堆

習題預習

1. 如何實現Heap的排序？
2. 如何找到Heap中的最大值或最小值？
3. 如何向Heap中添加一個新值？
4. 如何將Heap中的一個元素刪除？
5. 如何檢查一個數據結構是否符合Heap的性質？

說明知識

Heap是一種樹形資料結構，其中每個節點都具有一個值，並且擁有一個父節點和零個或多個子節點。Heap可以分為最小堆和最大堆兩種形式，最小堆中每個節點的值都比其子節點小，而最大堆中每個節點的值都比其子節點大。

舉例來說：

假設有以下一個最小堆：

     1    
   /    \  
 2       3  
/  \    /   \   

4 5 6 7

其中最小的元素是1，其它元素的值都比1大，而左子樹的元素都比右子樹的元素小，這就符合了最小堆的特性。

堆可以用來實現優先級隊列，通常使用陣列來實現。在堆中，基本操作包括插入新元素、刪除最小（或最大）元素、搜尋最小（或最大）元素等。堆排序也是一種使用堆的排序算法。

彙總重點

1. Heap是一種樹狀結構，通常用於實現優先級隊列。
2. Heap通常被實現為二叉堆，其中每個節點的值小於或大於其子節點的值（稱為小根堆或大根堆）。
3. Heap支持插入新元素和將最小或最大元素彈出的操作，這些操作的時間複雜度都是O(log n)。
4. Heap可以通過將一個數字附加到堆底並再次構建堆來實現排序。
5. 小根堆（或大根堆）可以用於Dijkstra算法和Kruskal算法等算法中，它們都需要尋找最小（或最大）權重邊或最小（或最大）路徑。
6. Heap還可以用於動態編程和排序算法，如堆排序和快速排序。

知識測驗

1. LeetCode 215. Kth Largest Element in an Array
2. LeetCode 502. IPO
3. LeetCode 973. K Closest Points to Origin
4. LeetCode 347. Top K Frequent Elements
5. LeetCode 295. Find Median from Data Stream

答案不提供，希望試著自己解決問題。