---
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 時，可能發生的上浮行為，細節請看註解

    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 時，可能發生的下沉行為，細節請看註解

    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 列表**

    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: `資料結構`