堆與堆排序#

堆的定義#

堆是一種特殊的完全二元樹，滿足：

1. 結構性質：完全二元樹（除最後一層外都填滿，最後一層靠左）
2. 堆性質：每個節點 >= 或 <= 其子節點

陣列存儲#

完全二元樹特別適合用陣列存儲（從索引 1 開始）：

若從索引 0 開始：左子 = 2*i+1，右子 = 2*i+2，父 = (i-1)/2

核心操作：堆化 (Heapify)#

上浮 (Sift Up) - 插入時使用#

def sift_up(heap, i):
    while i > 1 and heap[i] > heap[i // 2]:
        heap[i], heap[i // 2] = heap[i // 2], heap[i]
        i = i // 2

下沉 (Sift Down) - 刪除堆頂時使用#

def sift_down(heap, n, i):
    while True:
        max_pos = i
        if 2*i <= n and heap[2*i] > heap[max_pos]:
            max_pos = 2*i
        if 2*i+1 <= n and heap[2*i+1] > heap[max_pos]:
            max_pos = 2*i+1
        if max_pos == i:
            break
        heap[i], heap[max_pos] = heap[max_pos], heap[i]
        i = max_pos

時間複雜度：O(log n)

堆排序#

步驟#

flowchart LR
    subgraph 階段一["階段 1：建堆"]
        A1[無序陣列] --> A2[從最後一個<br/>非葉節點開始]
        A2 --> A3[逐一下沉]
        A3 --> A4[大頂堆完成]
    end

    subgraph 階段二["階段 2：排序"]
        B1[取堆頂] --> B2[與末尾交換]
        B2 --> B3[縮小堆範圍]
        B3 --> B4[堆頂下沉]
        B4 --> B5{堆為空?}
        B5 -->|否| B1
        B5 -->|是| B6[排序完成]
    end

    A4 --> B1

    style A4 fill:#e8f5e9
    style B6 fill:#e8f5e9

1. 建堆：將無序陣列建成大頂堆
2. 排序：反覆取堆頂放到末尾，縮小堆範圍

def heap_sort(arr):
    n = len(arr)

    # 建堆 - 從最後一個非葉節點開始下沉
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n - 1, i)

    # 排序 - 堆頂與末尾交換，縮小堆
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        sift_down(arr, i - 1, 0)

複雜度#

• 建堆：O(n)（不是 O(n log n)！）
• 排序：O(n log n)
• 空間：O(1)（原地排序）
• 穩定性：不穩定

堆排序 vs 快速排序：雖然都是 O(n log n)，但快排通常更快，因為：

1. 堆排序資料訪問是跳躍的，對 CPU 快取不友好
2. 建堆會打亂原有順序，增加交換次數

堆的應用#

1. 優先佇列 (Priority Queue)#

import heapq
pq = []
heapq.heappush(pq, 3)  # 插入
heapq.heappop(pq)       # 取出最小值

2. Top K 問題#

維護大小為 K 的小頂堆：

def topK(nums, k):
    heap = []
    for num in nums:
        if len(heap) < k:
            heapq.heappush(heap, num)
        elif num > heap[0]:
            heapq.heapreplace(heap, num)
    return heap

時間複雜度：O(n log k)

3. 求中位數（動態資料）#

使用兩個堆：

• 大頂堆：存較小的一半
• 小頂堆：存較大的一半
• 中位數 = 大頂堆的堆頂

延伸應用：同樣方法可求任意百分位數，如 P99 響應時間。