最大堆

最大堆（Max-Heap）是一種二叉堆，其中每個節點的值都不小於其子節點的值。最大堆可以是一棵完全二叉樹，也可以是一棵近似完全二叉樹的堆。在最大堆中，根節點是整個堆中最大的元素。

最大堆可以用於實現優先佇列，其中刪除最大元素（即堆頂元素）的過程可以通過一次旋轉操作將堆頂元素與最後一個元素交換，然後進行堆化（heaping），即恢復堆的性質，來保持O(log n)的時間複雜度。

最大堆的插入和構建過程如下：

1. 插入新元素時，將其添加到堆的最後一個位置。
2. 從堆的最後一個元素開始，向上檢查，直到到達根節點。
3. 如果新元素的父節點比它小，則交換父節點和新元素的位置。
4. 重複步驟3，直到新元素的位置滿足堆的性質（即新元素不小於其父節點），或者到達了根節點（此時新元素已經是堆頂，不需要再交換）。

最大堆的刪除最大元素（堆頂元素）的過程如下：

1. 將堆的最後一個元素與堆頂元素交換位置。
2. 刪除堆頂元素後，堆的形狀不再滿足堆的性質。
3. 從堆頂開始，向下檢查，直到到達最合適的子節點或者葉子節點。
4. 如果堆頂元素小於其左子節點或右子節點，則交換堆頂元素與其較大子節點的位置。
5. 重複步驟3和步驟4，直到堆的性質恢復，或者到達了葉子節點（此時堆頂元素已經是堆中最大的元素，不需要再交換）。

最大堆的時間複雜度取決於堆的實現方式。如果是數組實現的完全二叉樹形式的堆，插入和刪除最大元素的時間複雜度都是O(log n)。如果是鍊表實現的堆，時間複雜度可能會更高。