Ch6: Heapsort

本章節將利用 Heap 這個資料結構，來進行排序。

6-1 Heap

Heap 是一種特殊的 binary tree，其中可以分為 Max heap 與 Min heap：

• Max heap：每個 node 的 value 都大於等於他的 child nodes
  
• Min heap：每個 node 的 value 都小於等於他的 child nodes
  

通常我們會用 array 來儲存 heap 的資料：

6-2 Maintaining the Heap Property

當有新節點加入或者刪除節點時，Heap 會進行自動修復，讓 heap 保持特定性質堆積。本章節以 Max heap 為例

MAX-HEAPIFY 是一個維護 Max heap 的機制，原理大致如下：

• 時間複雜度：
  $O(\log n)$
• pseudo code：
  

6-3 Building a heap

• 時間複雜度：
  $O(n)$
• 因為不是每一個都需要一樣的 MAX-HEAPIFY 時間，平均下來的時間其實很快
  

6-4 The heapsort algorithm

• 時間複雜度：
  $O(n\log n)$
• 步驟：
  • 把 heap 的最大值拿出，放到最後面
  • 重複執行這個步驟直到排序完成
• 因為是原地排序，不用額外空間

6-5 Priority queue

• 一種 heap 的應用
• 應用：作業排程（scheduling）、圖論的 Dijkstra 演算法