最小堆

最小堆（Min Heap）是一種特殊的完全二叉樹，也稱為小頂堆，是堆的一種類型。堆通常被用來解決優先佇列的問題，其中最小堆總是保持最頂部的元素（根節點）是最小的。

最小堆的一些關鍵特性：

1. 堆頂（根節點）總是最小值。
2. 堆中的每個節點都不大於（或者小於）其父節點。
3. 最小堆是經過排序的，即堆中的每個子樹都是最小堆。
4. 最小堆的形狀是「斜向下的」，這意味著從根節點到葉子節點的路徑上，每個節點的值都小於（或者等於）其父節點的值。

最小堆的插入和刪除操作的時間複雜度都是O(log n)，其中n是堆中元素的數量。這是因為堆的內部結構是平衡的，所以對堆的任何操作都可以在log n的時間內完成。

最小堆的實現通常使用數組來實現，因為這樣可以在O(1)時間內訪問任一節點，並且可以通過交換數組中的元素來調整堆的形狀。

下面是一個簡單的最小堆的Python實現：

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, item):
        self.heap.append(item)
        self.bubble_up(len(self.heap) - 1)

    def bubble_up(self, i):
        while i // 2 > 0 and self.heap[i] < self.heap[i // 2]:
            self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]
            i = i // 2

    def extract_min(self):
        if not self.heap:
            return None
        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.sink_down(0)
        return min_val

    def sink_down(self, i):
        while 2 * i < len(self.heap):
            child = 2 * i
            if child + 1 < len(self.heap) and self.heap[child + 1] < self.heap[child]:
                child += 1
            if self.heap[i] <= self.heap[child]:
                break
            self.heap[i], self.heap[child] = self.heap[child], self.heap[i]
            i = child

    def __len__(self):
        return len(self.heap)

    def __str__(self):
        return str(self.heap)

# 測試代碼
heap = MinHeap()
heap.insert(10)
heap.insert(3)
heap.insert(5)
heap.insert(7)
print(heap)
print(heap.extract_min())
print(heap)

這段代碼定義了一個最小堆類，並提供了插入、刪除最小值、獲取堆的大小和列印堆的方法。測試代碼中，我們創建了一個最小堆，並插入了一些元素，然後提取了最小值，並列印了堆的狀態。