Heap

Heap 是一種特殊的「完全二元樹 (Complete Binary Tree)」結構，滿足 Heap 性質。他被常用來實作「優先佇列 (Priority Queue)」。

---

一、基本術語

名稱	說明
Heap	一個完全二元樹，滿足 Heap 性質
Max Heap	每個節點都大於或等於其子節點 (根為最大值)
Min Heap	每個節點都小於或等於其子節點 (根為最小值)
Heapify	將任意數組轉成 Heap 的運算過程
Priority Queue	基於 Heap 實作，能快速取出最大或最小值的組織

---

二、Heap 特性

• 完全二元樹：從左到右填滿，無間隙

• 親子節點關係：

  • 如果節點給定 index i (以 0 為基)：

    • 左子節點: 2i + 1

    • 右子節點: 2i + 2

    • 父節點: (i - 1) // 2

• 時間複雜度：

  • 插入 / 刪除：O(log n)

  • 取最大 / 最小值：O(1)

---

三、Heap 操作 (Python 範例)

1. 插入元素 (Insert)

def heap_push(heap, value):
    heap.append(value)
    i = len(heap) - 1
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] > heap[parent]:  # Max Heap
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

2. 移除最大值 (Pop)

def heap_pop(heap):
    if not heap:
        return None
    heap[0], heap[-1] = heap[-1], heap[0]
    max_val = heap.pop()
    i = 0
    while 2 * i + 1 < len(heap):
        left = 2 * i + 1
        right = 2 * i + 2
        max_child = left
        if right < len(heap) and heap[right] > heap[left]:
            max_child = right
        if heap[i] < heap[max_child]:
            heap[i], heap[max_child] = heap[max_child], heap[i]
            i = max_child
        else:
            break
    return max_val

---

四、Python 常用的 Heap 模組：heapq

Python 自來的 heapq 模組對應最小堆 (Min Heap)，如需 Max Heap 可對值加負號處理

import heapq

nums = [3, 1, 5, 7, 2]
heapq.heapify(nums)  # 轉成 Min Heap

heapq.heappush(nums, 0)
print(heapq.heappop(nums))  # 最小值 0

---

五、Heap 應用

• 優先队列 (Priority Queue)

• Top-K 問題 (Ex: 找出前 K 大或前 K 小值)

• Dijkstra 最短路算法

• Huffman Encoding

---

六、Heap vs BST (Binary Search Tree)

特性	Heap	Binary Search Tree
結構限制	完全二元樹	無限制
排序性質	只滿足根節點性質	全基於排序的結構
操作性能	快速取最大/最小	快速搜尋/插入/刪除
時間複雜度	插入/刪除 O(log n)	平均 O(log n)，最壞 O(n)

---

Heap 是一個很有效率的組織，重要在於需要持續操作 "取出最大/最小值"的場景，是優先队列與許多應用算法的核心基礎。