最小堆和最大堆

最小堆（Min Heap）和最大堆（Max Heap）是兩種特殊的堆數據結構。堆是一種完全二叉樹，其中每個節點的值都小於（最小堆）或大於（最大堆）其子節點。

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

1. 最小堆：每個父節點的值都不大於其子節點。堆頂的元素是整個堆中值最小的元素。
2. 最大堆：每個父節點的值都不小於其子節點。堆頂的元素是整個堆中值最大的元素。

最小堆和最大堆通常通過數組來實現，其中父節點和子節點的關係可以通過以下公式計算：

• 父節點的索引為 i，則左子節點的索引為 2i + 1，右子節點的索引為 2i + 2。
• 子節點的索引為 j，則父節點的索引為 (j - 1) / 2。

在最小堆和最大堆中，堆頂元素總是有序的：在最小堆中，堆頂元素是最小的；在最大堆中，堆頂元素是最大的。通過維護這個特性，可以在對堆進行插入和刪除操作時保持堆的特性不變。

最小堆和最大堆的一些常見操作包括：

• 插入（Insert）：將一個新的元素添加到堆的底部，然後通過向上調整（updating）操作將新元素移動到正確的位置。
• 刪除最小/最大元素（Extract Min/Max）：移除堆頂的元素，然後將最後一個元素放到堆頂，並通過向下調整（downward）操作將堆頂元素移動到正確的位置。
• 調整（Updating）：當堆的某個節點的值發生變化時，需要通過調整操作將堆的特性恢復。

最小堆和最大堆在許多算法和數據結構中都有套用，例如優先佇列、排序算法（如堆排序）等。