最大堆的刪除

最大堆（Max-Heap）是一種二叉堆，其中每個節點的值都不小於其子節點的值。最大堆通常用於優先佇列中，其中堆頂（根節點）的元素總是最大值。

要從最大堆中刪除最大元素（也稱為堆頂），我們需要執行以下步驟：

1. 找到堆頂元素，並將其與最後一個元素交換位置（因為刪除堆頂後，最後一個元素將成為新的堆頂）。
2. 檢查堆的平衡性。由於交換操作可能會破壞堆的性質，我們需要檢查堆頂的子節點是否仍然滿足堆的規則。如果堆頂的左子樹或右子樹比堆頂大，我們需要將較大的子節點與堆頂交換位置，並重複這一步直到堆的性質得到恢復。
3. 堆頂的子節點不再需要檢查後，我們需要將堆的大小減少1，並檢查堆頂的父節點是否違反堆的性質。如果父節點小於其左子節點或右子節點，我們需要將父節點與較大的子節點交換位置，並重複這一步直到堆的性質得到恢復。
4. 重複步驟3，直到堆的性質得到恢復。

這個過程可以用偽代碼表示如下：

function DeleteMax(heap):
    # 找到堆頂元素，並將其與最後一個元素交換位置
    swap heap[1] with heap[heap.length - 1]
    # 堆的大小減少1
    heap.length -= 1
    # 修復堆的性質
    maxHeapify(heap, 1)

函式maxHeapify用於修復堆的性質，其偽代碼如下：

function maxHeapify(heap, i):
    # 左孩子節點
    left = 2 * i
    # 右孩子節點
    right = left + 1
    # 最大孩子節點
    max = i
    # 如果左孩子存在且比父節點大
    if left < heap.length and heap[left] > heap[max]:
        max = left
    # 如果右孩子存在且比父節點大
    if right < heap.length and heap[right] > heap[max]:
        max = right
    # 如果最大孩子不是父節點，進行交換
    if max != i:
        swap heap[i] with heap[max]
        # 遞歸修復堆的性質
        maxHeapify(heap, max)

通過這種方式，我們可以從最大堆中刪除最大元素，並保持堆的性質。