---
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
### 最大二元堆積 - 規則
* 下圖為一個最大二元堆積表示圖；其中 **二元堆積** 就是說每個節點最多只會有兩個子節點，並且填充必須從左到右填充
> 允許有相同優先度元素
>
> 
1. **堆積順序**：**Parent Node 必須比左、右 Node 都還要大，++左右誰大則無關++**
2. **堆積狀態**：**第 K 層必須滿足 2^k^ 大小**，才能處理 K + 1 層的項目
> 如果要求總數量 (非完整二元)，有 K 層，則總數會在 (2^k^) ~ (2^K+1^ - 1) 之間
>
> 
* 有 N 個項目時 Heap 需要幾層才能完成存取 ? 這就跟 **log 對數** 有關
有 N 個項目時，需要 log(N) 層 (這是以根節點為第 0 層開始算)；N = 7 則 log(7) = 2.8，取整則為 2；N = 8 則 log(8) = 3，本身整數，則為 3
> log 使用 2 為底數
> 
### Heap 操作 - 插入 enqueue 上浮
* Heap 若是要插入新元素，則須將新元素放置對列尾部，透過 **++上浮操作++** (也就是向上層逐一比對交換)，最終得到結果
> 
以下為插入新元素 `14` 的上浮比較順序；上浮操作也有幾個需要注意的特點
1. 比較 14 > 11 ? 兩者交換，繼續上浮比較
> 
2. 比較 14 > 13 ? 兩者交換，繼續上浮比較
> 
:::info
* 這裡有個特點，需要關心另外一個子樹 9 的項目需要交換嗎 ?
不需要! 因為它已經按照規則進行過排序，代表 **9 已經小於原本的 Parent Node，所以就算新交換上去也可以正常運作**
:::
3. 比較 14 > 15 ? 不交換，最終完成 `enqueue` 整理
> 
:::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
> 
2. 儲存第 0 層 (Header) 最高優先項目
> 
3. 重整 Heap 列表
* 判斷左、右子樹，誰的優先序高則與其交換；相同、只有左子樹則與左邊交換交換一個 ( 相等時若與右邊交換則會導致樹不平衡
比較兩個子樹 14 == 14，挑選左邊進行交換
> 
比較兩個子樹 13 > 9，挑選左邊進行交換
> 
:::warning
* 如果比較項目比左、右都小，則需 **比較左右大小，挑選大的交換 !!**
:::
:::success
* **二元堆積，移除 `dequeue` 效能分析**：
**它的移動的次數就是 Heap 的高度 `O(log(N))`**，但比較次數則是 `O(2*log(N))` (比較左右子樹大小)，所以 **移除 `dequeue` 效能仍屬於 `O(log(N))` 的效能**
:::
## Array Heap
這裡為了簡化運算，會將 Array[0] 的位置空下，所以總數組長度為 Array.length
> 
* 上圖可以雖算出 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
> 
2. 子推父：求節點 storage[K] 的左右子節點
* **右、左 `storage[K / 2]` (無條件捨去)**；
假設 K 為 7，父節點為 storage[3]，值就是 14
假設 K 為 6，父節點為 storage[3]，值就是 14
> 
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));
}
}
}
```
> 
:::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));
}
}
}
```
從結果可以看出，它從 **大到小** 自動排出
> 
:::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: `資料結構`
Sign in with Wallet
Connect another wallet