概念

Heap 屬於樹狀結構的一種，特性是 parent 永遠比 child 大或小，最多只會有兩個 child

Max-Heap

父節點的值 > 子節點的值，root 是所有節點中最大的

MaxHeap1

Insert

新增新的節點到任何一個leaf底下，但如果比父節點大的話，需要不斷往上移(sift up)，直到滿足條件

example: Insert(32)

MaxHeap2

ExtractMax

提取最大的節點，隨便取一個leaf與root做交換，然後free掉該leaf

若換上來的新root不符合Max-Heap，需要將root不斷往下移(sift down)，直到滿足條件

  • 2個child都比root大，選最大的
  • 1個child比root大，選該child

符合Max-Heap則不需要移動

Remove

刪除某個節點，可利用ExtractMax，將該節點的值改成MAXVALUE(無限大)，執行check Max-Heap，該節點就會被移到root，這時候在執行ExtractMax

實作

處理Heap時，習慣用 Complete Binary Tree 的特性去維持結構，它可以簡單的用 Array 來表示

Complete Binary Tree: 除了leaf層，各層節點全滿，最後一層節點都靠左

所有operation只要 $O(logN)$ 的時間，GetMax只需 $O(1)$

MaxHeap3

如果 root 的 index 從 1 開始

  • parent(i) = i / 2
  • leftchild(i) = i * 2
  • rightchild(i) = i * 2 + 1

如果 root 的 index 從 0 開始

  • parent(i) = (i - 1) / 2
  • leftchild(i) = i * 2 + 1
  • rightchild(i) = i * 2 + 2

保持Complete Tree，新增節點時一律放在leap層的最左邊，做check Max-Heap，若不符合則往上移動(sift up)，直到滿足條件

Priority Queue

Heap的結構(Min/Max)使得它適合用來實作 Priority Queue 的概念

Priority Queue是指每一個element都附帶一個優先值，優先值越高的放在越前面

ChangePriority: 改變某個節點的 priority(就是改變節點的值)，檢查是否符合 Max-Heap，做上移或下移

複雜度比較

以插入新的值與取值來講 Heap 的綜合表現勝於 Array 與 List

Data Type Insert ExtractMax
Unsorted array / list $O(1)$ $O(N)$
Sorted array / list $O(N)$ $O(1)$
Binary Heap array $O(logN)$ $O(logN)$

pseudo code

BuildHeap

1
2
3
4
5
BuildHeap(A[1..n])
    size ← n
    // 只需做一半長度來建立Heap，是因為之後做SiftUp時去抓左右小孩就會cover到所有element
    for i from n/2 downto 1
        SiftDown(i)

SiftUp

1
2
3
4
5
SiftUp(i, Heap[1..n])
    // 不是root且比parent大
    while i > 1 and Heap[Parent(i)] < H[i]
        swap Heap[Parent(i)] and Heap(i)
        i ← Parent(i)

SiftDown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
SiftDown(i, Heap[1..n])
    maxIndex ← i
    /* 選最大的小孩交換 */
    l = LeftChild(i)
    if l <= size and Heap[l] > Heap[maxIndex]  // > for max-heap, < for min-heap
        maxIndex ← l

    r ← RightChild(i)
    if r <= size and Heap[r] > Heap[maxIndex]
        maxIndex ← r
    
    if i != maxIndex   // 需要做交換
        swap Heap[i] and Heap[maxIndex]
        SiftDown(maxIndex, Heap)   // 遞迴直到滿足條件

Insert

1
2
3
4
5
6
7
Insert(p, Heap[1..n])
    if size = maxSize
        return ERROR
    size ← size + 1
    Heap[size] ← p   // 新的節點加到最後一個位置 (leaf層空位)
    
    SiftUp(size, Heap);  // 檢查是否需要往上移

ExtractMax

1
2
3
4
5
6
ExtractMax(Heap[1..n])
    result ← Heap[1]  // 提取root的值
    Heap[1] ← Heap[size] // 把leaf層最後一個值放到root
    size = size - 1;  
    SiftDown(1, Heap)  // 檢查root是否需要往下移
    return result

Remove

1
2
3
4
Remove(i, Hea[1..n])
    Heap[i] ← MAXVALUE
    SiftUp(i)   // 因為被assign最大值，所以該節點會被移動到root
    ExtractMax(Heap)

ChangePriority

1
2
3
4
5
6
7
ChangePriority(i, p, Heap[1..n])
    oldp ← Heap[i]
    Heap[i] ← p
    if p > oldp
        SiftUp(o)
    else
        SiftDown(i)