最大堆和最小堆

最大堆和最小堆是兩種特殊的堆數據結構，它們分別用於存儲序列中的最大值或最小值。堆是一種完全二叉樹，其中每個節點都滿足堆屬性：在最大堆中，父節點的值總是不小於其子節點的值；在最小堆中，父節點的值總是不大於其子節點的值。

最大堆和最小堆的定義如下：

1. 最大堆（Max-Heap）：在最大堆中，每個節點的值都不小於其子節點的值。根節點是整個堆中最大的元素。最大堆也稱為大根堆（或優先堆）。

2. 最小堆（Min-Heap）：在最小堆中，每個節點的值都不大於其子節點的值。根節點是整個堆中最小的元素。最小堆也稱為小根堆。

最大堆和最小堆的實現通常使用數組來表示，因為數組可以很容易地模擬二叉樹的形狀。在數組中，父節點和子節點的關係可以通過下標計算得出：

• 對於最大堆，如果父節點的值小於其左子節點或右子節點的值，則需要交換父節點和子節點，以保持堆屬性。
• 對於最小堆，如果父節點的值大於其左子節點或右子節點的值，則需要交換父節點和子節點，以保持堆屬性。

堆排序算法就是利用最大堆或最小堆的特性來實現的。堆排序的基本步驟如下：

1. 構建一個最大堆或最小堆。
2. 將堆頂元素（最大或最小值）與數組的最後一個元素交換位置。
3. 調整堆頂以下的子樹，使其重新成為一個堆。
4. 重複步驟2和步驟3，直到堆的大小減少到1。

堆排序的時間複雜度為O(n log n)，其中n是數組的大小。最大堆和最小堆在許多程式語言的庫中都有實現，例如Java的Collections.sort()方法內部就使用了最小堆來排序。