最大堆

習題預習

1. 如何將一個數據插入到Max Heap中？
2. 如何從Max Heap中刪除最大值？
3. 如何構建Max Heap？
4. 如何查找Max Heap的最大值？
5. 如何使用Max Heap來協調一系列任務的執行順序？

說明知識

Max Heap是一種二元樹 (Binary Tree) 的數據結構，其中每個節點的值都大於其子樹中的節點值。也就是說，樹的根節點必須是樹中所有節點的最大值。在Max Heap中，對於任意的節點 i，其左子節點為 2i，右子節點為 2i+1。

以下是一個Max Heap的例子：

 70
/ \

50 60
/ \
30 40 20

在這個例子中，根節點為 70，其左子節點為 50，右子節點為 60。左子節點 50 的左右子節點分別為 30 和 40，右子節點 60 只有一個右子節點 20。

Max Heap通常用於實現堆排列 (Heap Sort)、優先佇列 (Priority Queue) 等數據運算中，也可以用於找到最小 K 個數中的最大值。

彙總重點

1. Max Heap 是一種二元樹，每個節點的值都大於等於其子節點的值。
2. Max Heap 是一種完全二元樹，即所有的節點都填滿了上層節點，最後一層從左到右填滿。
3. Max Heap 可以使用一維陣列來實現，根節點的索引為 0，其左子節點的索引為 2i+1，右子節點的索引為 2i+2。
4. Max Heap 常用的操作包括插入元素、刪除最大值、建立 Max Heap 和排序等。
5. 在插入元素時，先把元素插入到堆的最後一個位置，然後進行上浮操作，將其和父節點的值進行比較，如果比父節點大，則交換位置，直到到達根節點或比父節點小為止。
6. 在刪除最大值時，先將根節點和最後一個節點交換位置，然後進行下沉操作，將其和子節點的值進行比較，如果比子節點小，就和子節點交換位置，直到下沉到最後一層或比子節點大為止。
7. 建立 Max Heap 的方法可以使用逐步下沉的方式，從最後一個有子節點的節點開始，對每個節點進行下沉操作，使其成為子樹的最大值。
8. Max Heap 的排序算法稱為 Heap Sort，是一種不穩定的排序算法，時間複雜度為 O(n log n)。
9. Max Heap 也可以用來實現優先隊列，每次取出最大值即可得到優先級最高的元素。

知識測驗

1. 找到第 k 大的元素
   給定一個大小爲 n 的整數數組，請找到第 k 大的元素。可以假設 1 ≤ k ≤ n。

答案：使用最大堆維護數組的前 k 大元素，然後返回堆頂元素即可。

2. 合併 k 個有序數組
   給定 k 個已經按照升序排列的數組，請將它們合併成一個新的有序數組。

答案：建立一個大小爲 k 的最小堆，每次將 k 個數組中的最小元素加入堆中，然後彈出堆頂元素並添加到結果數組中，直到堆為空。

3. 求解中位數
   給定一個數組，求解其中位數（如果數組大小為偶數，則返回中間兩個數的平均值）。

答案：使用兩個堆，一個最大堆維護數組的前半部分，一個最小堆維護數組的後半部分。當數組大小爲奇數時，中位數就是最大堆的堆頂，當數組大小爲偶數時，中位數就是最大堆的堆頂和最小堆的堆頂的平均值。

4. 找到 k 個最接近的元素
   給定一個排序後的數組和一個數 k，請找到 k 個和指定數最接近的元素。可以假設給定數字一定存在於數組中。

答案：使用大小爲 k 的最小堆維護 k 個距離最近的元素。每次加入一個新元素時，如果堆大小小於 k，就直接加入，否則就判斷新元素是否比堆頂元素更接近，如果是則彈出堆頂元素並加入新元素。

5. 找到多數元素
   給定一個大小爲 n 的整數數組，請找到出現次數超過 ⌊ n/2 ⌋ 的元素。

答案：使用大小爲 n/2+1 的最小堆（或最大堆），將數組中的元素加入堆中。由於最多只有一個元素的出現次數超過 ⌊ n/2 ⌋，所以堆頂元素一定是答案。