--- # System prepended metadata title: Heap 堆積 tags: [資料結構] --- --- title: 'Heap 堆積' disqus: kyleAlien --- Heap 堆積 === ## OverView of Content 堆積跟 **優先序有關係**，有分最小堆積、最大堆積 [TOC] ## Heap 堆積 - 概述 Heap 的特色有： 1. 資料有優先順率 2. O(1) 的速度找到優先度最高的值 3. O(logN) 的速度移除最高優先度值 4. 以 O(N) 速度入隊列 ### Queue & Heap * Queue 是一種先進先出 (FIFO) 的結構，它可以達到 `enqueue`、`dequeue` 兩個行為皆是 O(1) 的效率，**但是如果 Queue 要判別優先度，`dequeue` 最差則會降至 O(N)** > 因為 `dequeue` 需要比較每個原素的優先序 ## 最大二元堆積 以下會以一個堆積最大尺寸 M (一般 Array)，來儲存一個 N 大小的項目，其中 N < M ### 最大二元堆積 - 規則 * 下圖為一個最大二元堆積表示圖；其中 **二元堆積** 就是說每個節點最多只會有兩個子節點，並且填充必須從左到右填充 > 允許有相同優先度元素 > > ![](https://i.imgur.com/Z4ySn8F.png) 1. **堆積順序**：**Parent Node 必須比左、右 Node 都還要大，++左右誰大則無關++** 2. **堆積狀態**：**第 K 層必須滿足 2^k^ 大小**，才能處理 K + 1 層的項目 > 如果要求總數量 (非完整二元)，有 K 層，則總數會在 (2^k^) ~ (2^K+1^ - 1) 之間 > > ![](https://i.imgur.com/boV6l00.png) * 有 N 個項目時 Heap 需要幾層才能完成存取 ? 這就跟 **log 對數** 有關 有 N 個項目時，需要 log(N) 層 (這是以根節點為第 0 層開始算)；N = 7 則 log(7) = 2.8，取整則為 2；N = 8 則 log(8) = 3，本身整數，則為 3 > log 使用 2 為底數 > ![](https://i.imgur.com/9cCKqCo.png) ### Heap 操作 - 插入 enqueue 上浮 * Heap 若是要插入新元素，則須將新元素放置對列尾部，透過 **++上浮操作++** (也就是向上層逐一比對交換)，最終得到結果 > ![](https://i.imgur.com/Bcyahmb.png) 以下為插入新元素 `14` 的上浮比較順序；上浮操作也有幾個需要注意的特點 1. 比較 14 > 11 ? 兩者交換，繼續上浮比較 > ![](https://i.imgur.com/ZS3BBEn.png) 2. 比較 14 > 13 ? 兩者交換，繼續上浮比較 > ![](https://i.imgur.com/vENTDGz.png) :::info * 這裡有個特點，需要關心另外一個子樹 9 的項目需要交換嗎 ? 不需要! 因為它已經按照規則進行過排序，代表 **9 已經小於原本的 Parent Node，所以就算新交換上去也可以正常運作** ::: 3. 比較 14 > 15 ? 不交換，最終完成 `enqueue` 整理 > ![](https://i.imgur.com/FznwcJc.png) :::success * **二元堆積，插入 `enqueue` 效能分析**： 有沒有發現 **它比較的次數就是 Heap 的高度**! 我們前面已經有分析過，Heap 高度就是 `O(logN)`，因此 **二元堆積 `enqueue` 的效能也同樣是 `O(logN)`** ::: ### Heap 操作 - 移除 dequeue 下沉 * 移除最高優先度元素，其實就是取出 Heap 最前面的元素，但在之後仍需整理 Heap 列表 (不能讓 Header 為空)，其步驟如下 1. 移除 Heap 中最後一個元素，之後會替換第 0 層 (Header) 2. 儲存第 0 層 (Header) 最高優先項目的序號，方便之後回傳 3. 重整 Heap 列表 * 移除 `dequeue` 順序概念圖如下 1. 移除最尾端元素 11 > ![](https://i.imgur.com/CoVR3Uh.png) 2. 儲存第 0 層 (Header) 最高優先項目 > ![](https://i.imgur.com/ii7GMyY.png) 3. 重整 Heap 列表 * 判斷左、右子樹，誰的優先序高則與其交換；相同、只有左子樹則與左邊交換交換一個 ( 相等時若與右邊交換則會導致樹不平衡 比較兩個子樹 14 == 14，挑選左邊進行交換 > ![](https://i.imgur.com/NGyvYTH.png) 比較兩個子樹 13 > 9，挑選左邊進行交換 > ![](https://i.imgur.com/53pcIcQ.png) :::warning * 如果比較項目比左、右都小，則需 **比較左右大小，挑選大的交換 !!** ::: :::success * **二元堆積，移除 `dequeue` 效能分析**： **它的移動的次數就是 Heap 的高度 `O(log(N))`**，但比較次數則是 `O(2*log(N))` (比較左右子樹大小)，所以 **移除 `dequeue` 效能仍屬於 `O(log(N))` 的效能** ::: ## Array Heap 這裡為了簡化運算，會將 Array[0] 的位置空下，所以總數組長度為 Array.length > ![](https://i.imgur.com/is40zNr.png) * 上圖可以雖算出 Parent Node、Child Node 之間的關係，並用數學式表示；假設 Array 名稱為 storage[] 1. 父推子：求節點 storage[K] 的左右子節點 * **左 `storage[K * 2]`**；假設 K 為 3，左節點為 storage[6]，值就是 12 * **右 `storage[K * 2 + 1]`**；假設 K 為 4，右節點為 storage[9]，值就是 2 > ![](https://i.imgur.com/fBFMSm2.png) 2. 子推父：求節點 storage[K] 的左右子節點 * **右、左 `storage[K / 2]` (無條件捨去)**； 假設 K 為 7，父節點為 storage[3]，值就是 14 假設 K 為 6，父節點為 storage[3]，值就是 14 > ![](https://i.imgur.com/GTWggpi.png) 3. **index K 有效範圍是 0 <= K <= N**：超出該範圍，K 無效，也就超出 Heap ### enqueue 實作 - swim 上浮 * 接下來我們實作 enqueue 時，可能發生的上浮行為，細節請看註解 ```java= public class Heap { private final Integer[] storage; private int cur; // 用來記錄當前儲存的元素數量 public Heap(int size) { storage = new Integer[size + 1]; // + 1 是因為我們會空下 [0] cur = 0; } public void enqueue(int newVal) { if(cur == storage.length - 1) { // 容量只有原大小 - 1 throw new RuntimeException("Array already full."); } cur += 1; storage[cur] = newVal; // 放入數組最後 swim(cur); } public void swim(int index) { while (index > 1) { // > 1 是因為我們空下 [0] // 算出父節點 index int compareIndex = index / 2; int compareVal = storage[compareIndex]; // 與父節點數值做比較，小於父節點就代表上面的也不用再交換 if(storage[index] < compareVal) { break; } // 交換數值 swap(index, compareIndex); index = compareIndex; } } // 交換 i & j 的數值 public void swap(int i, int j) { int tmp = storage[i]; storage[i] = storage[j]; storage[j] = tmp; } public static void main(String[] args) { // 已排列好的 Heap int[] a = {15, 13, 14, 9, 11, 12, 14, 8, 2, 6}; Heap heap = new Heap(a.length); for (int i : a) { heap.enqueue(i); System.out.println("Array: " + Arrays.toString(heap.storage)); } } } ``` > ![](https://i.imgur.com/S6PZeqC.png) :::success * 其中我們可以保證 `swap` 函數的執行次數必定不會大於 `log(N)` (N 為 Heap 數量) ::: ### dequeue 實作 - sink 下沉 * 接下來我們實作 dequeue 時，可能發生的下沉行為，細節請看註解 ```java= public class Heap { private final Integer[] storage; private int cur; // 用來記錄當前儲存的元素數量 public Heap(int size) { storage = new Integer[size + 1]; // + 1 是因為我們會空下 [0] cur = 0; } ... 省略 enqueue public void swap(int i, int j) { int tmp = storage[i]; storage[i] = storage[j]; storage[j] = tmp; } public int dequeue() { if(cur == 0) { // 判斷是否有元素可取 throw new RuntimeException("No value in heap now."); } int top = storage[1]; // 保留 top 值 storage[1] = storage[cur]; // 最後元素放置第一，開始準備下沉 storage[cur] = null; // 將原本最後的元素至為 null cur -= 1; // 減去 cur sink(); return top; } public void sink() { int rootIndex = 1; // 從頂端下沉 while (rootIndex * 2 + 1 <= cur) { // 判斷是否越界 int rootVal = storage[rootIndex]; // root 取左右 int leftIndex = 2 * rootIndex; int rightIndex = 2 * rootIndex + 1; int swapIndex = leftIndex; // 預設為左 // 比較左右，取最大的 index if(storage[leftIndex] < storage[rightIndex]) { swapIndex = rightIndex; // 發現右邊較大，則換右的 index } // 判斷 root 是否比要交換的元素大 if(rootVal > storage[swapIndex]) { // root 比較大，則後面不需要再交換 break; } swap(rootIndex, swapIndex); // 交換 rootIndex = swapIndex; } } public static void main(String[] args) { int[] a = {15, 13, 14, 9, 11, 12, 14, 8, 2, 6}; Heap heap = new Heap(a.length); for (int i : a) { heap.enqueue(i); } for (int j = 1; j < heap.storage.length; j++) { int top = heap.dequeue(); System.out.println("top: " + top); System.out.println("Array: " + Arrays.toString(heap.storage)); } } } ``` 從結果可以看出，它從 **大到小** 自動排出 > ![](https://i.imgur.com/PuuWF2N.png) :::success * 其中我們可以保證 `sink` 函數的執行次數必定不會大於 `log(N)` (N 為 Heap 數量) ::: ### 幾何大小調整 * 如同雜湊表 HashTable 一樣，可以使用幾何的方式調整列表，在調整完後 **將原數據重新入 Heap 列表** ```java= public void enqueue(int newVal) { if(cur == storage.length - 1) { // 進行大小調整 resize(); } cur += 1; storage[cur] = newVal; swim(cur); } public void resize() { int oldSize = storage.length; Integer[] tmp = storage; storage = new Integer[oldSize * 2]; // 幾何大小調整 cur = 0; for(int i = 1; i < tmp.length; i++) { if(tmp[i] == null) continue; enqueue(tmp[i]); } } ``` :::info * 這裡就不關注 threshold 伐值，直接進行幾何大小調整 * **再次入隊 `enqueue` 的 BIG O 仍為 O(log (N))** ::: ## Appendix & FAQ :::info ::: ###### tags: `資料結構`