最小堆刪除

最小堆（Min Heap）是一種特殊的完全二叉樹，其中每個節點的值都不大於其父節點的值。最小堆的根節點總是整個堆中值最小的元素。刪除最小堆的根節點（即堆中最小的元素）需要遵循以下步驟：

1. 找到最小堆的根節點（最小元素）。
2. 刪除根節點。
3. 如果最小堆不為空，將最小堆的最後一個元素放在根節點的位置。
4. 調整堆結構，確保新的根節點仍然是堆的一部分。

這個過程可以通過遞歸地調整堆的子樹來實現，直到堆結構恢復為最小堆為止。這個過程稱為堆的「下沉」（sinking）或「修復」（fix）。

以下是刪除最小堆根節點的偽代碼：

def delete_min(heap):
    if not heap:
        return None  # 堆為空，無法刪除

    # 找到並刪除最小元素
    min_element = heap[0]
    del heap[0]

    # 堆不為空，將最後一個元素放到根節點
    if len(heap) > 0:
        heap[0] = heap[-1]
        del heap[-1]

    # 調整堆結構
    sink(heap, 0)

    return min_element

def sink(heap, i):
    # 停止條件：當前節點已經是葉子節點或者其子節點都大於它
    while i < len(heap) // 2:
        # 找到左子樹和右子樹中較小的一個
        smallest = i
        if heap[smallest] > heap[2*i + 1]:
            smallest = 2*i + 1
        if heap[smallest] < heap[2*i + 2]:
            smallest = 2*i + 2

        # 交換當前節點和較小子節點
        if smallest != i:
            heap[i], heap[smallest] = heap[smallest], heap[i]
            i = smallest
        else:
            break

這段代碼定義了delete_min函式，它首先刪除最小堆的根節點，然後調用sink函式來調整堆結構。sink函式遞歸地向下移動節點，直到找到正確的位置，使得堆保持最小堆的性質。

請注意，這個算法假設最小堆是通過數組實現的，其中父節點的索引是子節點索引的一半，即parent(i) = i // 2，left(i) = 2*i + 1，right(i) = 2*i + 2。在實際套用中，你可能需要根據你的數據結構和實現方式來調整這個算法。