# 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 演算法