堆（Heap）：高效的優先級隊列實現

什么是堆？

堆是一種特殊的完全二叉樹，滿足以下性質：

堆序性：每個節點的值與其子節點滿足特定關系
- 最小堆：父節點 ≤ 子節點（根最小）
- 最大堆：父節點 ≥ 子節點（根最大）
結構性：完全二叉樹，除最后一層外完全填充，最后一層左對齊

最小堆：[1]/   \[3]     [2]/ \     /
[5][9] [4]最大堆：[9]/   \[5]     [8]/ \     /
[2][4] [3]

為什么需要堆結構？

高效極值訪問：O(1)時間獲取最小/最大值
動態優先級管理：實時處理優先級變化的數據
空間效率：可用數組緊湊存儲（無指針開銷）
算法優化：堆排序、Dijkstra算法等核心組件

堆的核心操作與復雜度

操作	時間復雜度	空間復雜度
構建堆	O(n)	O(1)
插入元素	O(log n)	O(1)
提取極值	O(log n)	O(1)
查看極值	O(1)	O(1)
刪除任意元素	O(log n)	O(1)
修改元素值	O(log n)	O(1)

堆的數組表示

完全二叉樹特性使得堆可以用數組高效存儲：

父節點索引：parent(i) = (i-1)//2
左子節點索引：left(i) = 2*i + 1
右子節點索引：right(i) = 2*i + 2

示例：

最大堆:70/    \50     60/ \    / \30 20  10 40數組表示: [70, 50, 60, 30, 20, 10, 40]

基本操作實現

1、上浮（Heapify Up）

def heapify_up(heap, i):while i > 0:parent = (i - 1) // 2if heap[i] > heap[parent]:  # 最大堆示例heap[i], heap[parent] = heap[parent], heap[i]i = parentelse:break

（1）初始狀態（插入新節點）

假設當前最大堆的數組為 [9, 5, 8, 3, 4, 2]，結構如下：

          [9]/   \[5]     [8]/ \     /[3][4] [2]

現在插入一個新節點?10 到堆的末尾，數組變為 [9, 5, 8, 3, 4, 2, 10]，破壞了堆性質：

          [9]/   \[5]     [8]/ \     / \[3][4]  [2] [10]   ← 節點10需要上浮

（2）執行?`heapify_up(heap, i=6)`?的分步圖解

（i=6 是新節點 10 的索引）

第1次循環：

找到父節點：
- parent = (6-1)//2 = 2（節點8）
- 比較?heap=10?和?heap=8：10 > 8?→ 需要交換
交換并更新：
- 交換?heap?和?heap（10 ? 8）
- 數組變為?[9, 5, 10, 3, 4, 2, 8]
- i?更新為?parent = 2（繼續檢查節點10）

          [9]/   \[5]     [10]     ← 節點10上浮到這里/ \     / \[3][4] [2][8]      ← 原節點8下沉

第2次循環：

找到新的父節點：
- parent = (2-1)//2 = 0（節點9）
- 比較?heap=10?和?heap=9：10 > 9?→ 需要交換
交換并更新：
- 交換?heap?和?heap（10 ? 9）
- 數組變為?[10, 5, 9, 3, 4, 2, 8]
- i?更新為?parent = 0（到達根節點）

          [10]         ← 節點10成為新根/   \[5]     [9]      ← 節點9下沉/ \     / \[3][4]  [2] [8]

終止條件：

現在?i=0（根節點），循環終止。

（3）最終最大堆

數組為 [10, 5, 9, 3, 4, 2, 8]，結構如下：

          [10]         ← 根節點最大/   \[5]     [9]      ← 每個父節點 ≥ 子節點/ \     / \[3][4] [2][8]

（4）關鍵點總結：

heapify_up?的作用：從節點?i?開始，通過不斷與父節點比較并交換，使其上浮到正確位置。
觸發場景：通常在插入新元素后調用（先追加到末尾，再上浮）。
終止條件：當節點?i?到達根節點，或父節點已經更大時停止。
時間復雜度：最壞情況從葉子上浮到根，為 O(log n)。

（5）對比?`heapify_down`?和?`heapify_up`：

操作	方向	典型場景	比較對象
`heapify_up`	上浮	插入新節點	只比較父節點
`heapify_down`	下沉	刪除根節點或修復堆	比較兩個子節點

2、下沉（Heapify Down）

def heapify_down(heap, n, i):while True:left = 2 * i + 1right = 2 * i + 2largest = iif left < n and heap[left] > heap[largest]:largest = leftif right < n and heap[right] > heap[largest]:largest = rightif largest != i:heap[i], heap[largest] = heap[largest], heap[i]i = largestelse:break

（1）初始最大堆（已破壞）

假設我們有一個部分破壞的堆（只有根節點不滿足堆性質），數組表示為 [3, 9, 8, 5, 4, 2]，結構如下：

          [3]          ← 根節點值(3)比子節點(9,8)小，需要下沉/   \[9]     [8]/ \     /[5][4] [2]

（2）執行?`heapify_down(heap, n=6, i=0)`?的分步圖解

第1次循環：

比較根節點和子節點：
- left = 2*0+1 = 1（值=9）
- right = 2*0+2 = 2（值=8）
- largest?初始為?0（值=3）
- 比較發現?left(9) > largest(3)?→?largest = left = 1
- right(8) > largest(9)？否，保持?largest=1
交換并更新：
- 交換?heap?和?heap（3 ? 9）
- 數組變為?[9, 3, 8, 5, 4, 2]
- i?更新為?largest = 1（繼續檢查節點3）

          [9]          ← 根節點已修復/   \[3]     [8]      ← 節點3需要繼續下沉/ \     /[5][4] [2]

第2次循環：

檢查新的 i=1（值=3）：
- left = 2*1+1 = 3（值=5）
- right = 2*1+2 = 4（值=4）
- largest?初始為?1（值=3）
- left(5) > largest(3)?→?largest = left = 3
- right(4) > largest(5)？否，保持?largest=3
交換并更新：
- 交換?heap?和?heap（3 ? 5）
- 數組變為?[9, 5, 8, 3, 4, 2]
- i?更新為?largest = 3（繼續檢查節點3）

          [9]/   \[5]     [8]      ← 節點5已滿足堆性質/ \     /[3][4] [2]         ← 節點3是葉子節點，無需處理

終止條件：

現在?i=3?是葉子節點（無子節點），largest == i，循環終止。

（3）最終最大堆

數組為 [9, 5, 8, 3, 4, 2]，結構如下：

          [9]          ← 根節點最大/   \[5]     [8]      ← 每個父節點 ≥ 子節點/ \     /[3][4] [2]

（4）關鍵點總結：

heapify_down?的作用：從節點?i?開始，通過不斷與更大的子節點交換，使其下沉到正確位置。
終止條件：當節點?i?沒有子節點，或已經比子節點大時停止。
時間復雜度：最壞情況從根下沉到葉子，為 O(log n)。

3、插入元素

def heappush(heap, item):heap.append(item)heapify_up(heap, len(heap)-1)

heappush?用于向堆中插入一個新元素，并維護堆的性質。它分為兩步：

heap.append(item)：將新元素添加到堆的末尾（保持完全二叉樹的結構性）。
heapify_up(heap, len(heap)-1)：從新插入的節點開始，向上調整（heapify_up），直到滿足堆序性。

分步圖解

假設當前有一個 最大堆，初始數組為 [10, 5, 9, 3, 4, 2, 8]，結構如下：

          [10]/    \[5]      [9]/ \      / \[3][4]   [2] [8]

現在要插入一個新元素 7。

Step 1:?`heap.append(7)`

將 7 添加到堆的末尾，數組變為 [10, 5, 9, 3, 4, 2, 8, 7]，結構如下：

          [10]/    \[5]      [9]/ \      / \[3][4]   [2] [8]/[7]       ← 新插入的節點7（索引=7）

此時，7 的父節點是 3（索引 (7-1)//2 = 3），由于 7 > 3，破壞了最大堆性質（父節點應 ≥ 子節點），需要調整。

Step 2:?`heapify_up(heap, i=7)`

第一次循環：
- i = 7（節點7）
- parent = (7-1)//2 = 3（節點3）
- 比較?heap = 7?和?heap = 3，發現?7 > 3，需要交換。
- 交換?7?和?3，數組變為?[10, 5, 9, 7, 4, 2, 8, 3]。
- i?更新為?parent = 3（現在?7?位于索引3）。

          [10]/    \[5]      [9]/ \      / \[7][4]   [2] [8]/[3]

第二次循環：
- i = 3（節點7）
- parent = (3-1)//2 = 1（節點5）
- 比較?heap = 7?和?heap = 5，發現?7 > 5，需要交換。
- 交換?7?和?5，數組變為?[10, 7, 9, 5, 4, 2, 8, 3]。
- i?更新為?parent = 1（現在?7?位于索引1）。

          [10]/    \[7]      [9]/ \      / \[5][4]   [2] [8]/[3]

第三次循環：
- i = 1（節點7）
- parent = (1-1)//2 = 0（節點10）
- 比較?heap = 7?和?heap = 10，發現?7 ≤ 10，停止調整（堆序性已滿足）。

最終堆

調整后的數組為 [10, 7, 9, 5, 4, 2, 8, 3]，結構如下：

          [10]         ← 根節點最大/    \[7]      [9]      ← 每個父節點 ≥ 子節點/ \      / \[5][4]  [2][8]/[3]

關鍵點總結

heappush?的作用：
- 在堆的末尾插入新元素，然后通過?heapify_up?調整堆序性。
時間復雜度：
- append?是 O(1)，heapify_up?是 O(log n)，所以總時間復雜度是?O(log n)。
適用場景：
- 適用于動態插入元素的場景（如優先隊列）。
對比?heappop：
- heappop?是刪除堆頂元素，并用最后一個元素替換，再?heapify_down?調整。

完整代碼示例（最大堆）

def heapify_up(heap, i):while i > 0:parent = (i - 1) // 2if heap[i] > heap[parent]:  # 最大堆：子節點 > 父節點則交換heap[i], heap[parent] = heap[parent], heap[i]i = parentelse:breakdef heappush(heap, item):heap.append(item)heapify_up(heap, len(heap) - 1)# 示例用法
heap = [10, 5, 9, 3, 4, 2, 8]
heappush(heap, 7)
print(heap)  # 輸出: [10, 7, 9, 5, 4, 2, 8, 3]

4、提取極值

def heappop(heap):if not heap:raise IndexError("heap is empty")root = heap[0]heap[0] = heap[-1]heap.pop()heapify_down(heap, len(heap), 0)return root

heappop 用于刪除并返回堆頂元素（最大值或最小值），同時維護堆的性質。它分為以下幾步：

檢查堆是否為空，若為空則拋出異常。
保存堆頂元素（root = heap），用于最后返回。
將堆末尾元素移到堆頂（heap = heap[-1]），并刪除末尾元素（heap.pop()）。
從堆頂開始向下調整（heapify_down），恢復堆序性。

分步圖解

假設當前有一個 最大堆，初始數組為 [10, 7, 9, 5, 4, 2, 8, 3]，結構如下：

          [10]         ← 堆頂（待刪除）/    \[7]      [9]/ \      / \[5][4]  [2][8]/[3]

Step 1: 刪除堆頂并替換為末尾元素

保存堆頂?root = 10（待返回）。
將末尾元素?3?移到堆頂，并刪除末尾元素：
- 數組變為?[3, 7, 9, 5, 4, 2, 8]。

          [3]          ← 新堆頂（原末尾元素3）/    \[7]      [9]/ \      / \[5][4]   [2] [8]

此時堆序性被破壞（3 比子節點 7 和 9 小），需要調整。

Step 2:?`heapify_down(heap, n=7, i=0)`

從堆頂 i=0（節點3）開始下沉：

第一次循環：
- left = 2*0+1 = 1（節點7），right = 2*0+2 = 2（節點9）。
- largest?初始為?0（節點3）。
- 比較?left(7) > largest(3)?→?largest = left = 1。
- 比較?right(9) > largest(7)?→?largest = right = 2。
- 交換?heap?和?heap（3 ? 9），數組變為?[9, 7, 3, 5, 4, 2, 8]。
- i?更新為?largest = 2（繼續檢查節點3）。

          [9]          ← 節點9上浮到堆頂/    \[7]      [3]     ← 節點3需要繼續下沉/ \      / \[5][4]   [2] [8]

第二次循環：
- left = 2*2+1 = 5（節點2），right = 2*2+2 = 6（節點8）。
- largest?初始為?2（節點3）。
- 比較?left(2) > largest(3)？否。
- 比較?right(8) > largest(3)?→?largest = right = 6。
- 交換?heap?和?heap（3 ? 8），數組變為?[9, 7, 8, 5, 4, 2, 3]。
- i?更新為?largest = 6（繼續檢查節點3）。

          [9]/    \[7]      [8]     ← 節點8上浮/ \      / \[5][4]   [2] [3]    ← 節點3是葉子節點，無需處理

終止條件：
- i=6?是葉子節點，largest == i，循環終止。

最終堆

調整后的數組為 [9, 7, 8, 5, 4, 2, 3]，結構如下：

          [9]          ← 新的堆頂/    \[7]      [8]     ← 每個父節點 ≥ 子節點/ \      / \[5][4]   [2] [3]

返回的堆頂元素是 10（已被刪除）。

關鍵點總結

heappop?的作用：
- 刪除堆頂元素，并用末尾元素替換，再通過?heapify_down?恢復堆序性。
時間復雜度：
- pop?和替換是 O(1)，heapify_down?是 O(log n)，總時間復雜度為?O(log n)。
適用場景：
- 適用于需要動態獲取最大值或最小值的場景（如優先隊列）。
對比?heappush：
- heappush?在末尾插入后上浮，heappop?在堆頂刪除后下沉。

完整代碼示例（最大堆）

def heapify_down(heap, n, i):while True:left = 2 * i + 1right = 2 * i + 2largest = iif left < n and heap[left] > heap[largest]:largest = leftif right < n and heap[right] > heap[largest]:largest = rightif largest != i:heap[i], heap[largest] = heap[largest], heap[i]i = largestelse:breakdef heappop(heap):if not heap:raise IndexError("heap is empty")root = heap[0]heap[0] = heap[-1]heap.pop()heapify_down(heap, len(heap), 0)return root# 示例用法
heap = [10, 7, 9, 5, 4, 2, 8, 3]
max_val = heappop(heap)
print("Popped:", max_val)  # 輸出: Popped: 10
print("Heap after pop:", heap)  # 輸出: Heap after pop: [9, 7, 8, 5, 4, 2, 3]

堆的構建

1. 自頂向下構建（O(n log n)）

def build_heap_slow(items):heap = []for item in items:heappush(heap, item)return heap

`build_heap_slow`?操作解析（最大堆示例）

build_heap_slow 通過逐個插入元素（heappush）的方式構建堆。雖然邏輯簡單，但時間復雜度較高（O(n?log?n)），因此稱為“慢速建堆”。

分步圖解

假設輸入數組為 [3, 1, 6, 5, 2, 4]，逐步構建最大堆：

初始狀態

heap = []

Step 1: 插入 3

heappush(heap, 3)?→?heap =

[3]

Step 2: 插入 1

heappush(heap, 1)?→?heap = [3, 1]

   [3]/
[1]

Step 3: 插入 6

先追加到末尾：heap = [3, 1, 6]
heapify_up(heap, 2)：
- 比較?6?和父節點?3（parent = (2-1)//2 = 0），6 > 3?→ 交換。
- heap = [6, 1, 3]

   [6]/   \
[1]   [3]

Step 4: 插入 5

先追加到末尾：heap = [6, 1, 3, 5]
heapify_up(heap, 3)：
- 比較?5?和父節點?1（parent = (3-1)//2 = 1），5 > 1?→ 交換。
- heap = [6, 5, 3, 1]

      [6]/   \[5]    [3]/
[1]

Step 5: 插入 2

先追加到末尾：heap = [6, 5, 3, 1, 2]
heapify_up(heap, 4)：
- 比較?2?和父節點?5（parent = (4-1)//2 = 1），2 ≤ 5?→ 停止。

heap?保持不變：

      [6]/   \[5]    [3]/ \
[1] [2]

Step 6: 插入 4

先追加到末尾：heap = [6, 5, 3, 1, 2, 4]
heapify_up(heap, 5)：
- 比較?4?和父節點?3（parent = (5-1)//2 = 2），4 > 3?→ 交換。
- heap = [6, 5, 4, 1, 2, 3]

      [6]/   \[5]    [4]/ \    /
[1][2] [3]

最終堆

數組為 [6, 5, 4, 1, 2, 3]，結構如下：

      [6]         ← 根節點最大/   \[5]    [4]      ← 每個父節點 ≥ 子節點/ \    /
[1][2] [3]

關鍵點總結

時間復雜度：
- 每次?heappush?是 O(log n)，共 n 次操作 →?O(n log n)。
空間復雜度：
- 需要額外空間存儲堆 → O(n)。
對比快速建堆（Floyd算法）：
- 快速建堆直接從最后一個非葉子節點開始?heapify_down，時間復雜度為 O(n)。

完整代碼示例（最大堆）

def heapify_up(heap, i):while i > 0:parent = (i - 1) // 2if heap[i] > heap[parent]:  # 最大堆：子節點 > 父節點則交換heap[i], heap[parent] = heap[parent], heap[i]i = parentelse:breakdef heappush(heap, item):heap.append(item)heapify_up(heap, len(heap) - 1)def build_heap_slow(items):heap = []for item in items:heappush(heap, item)return heap# 示例用法
items = [3, 1, 6, 5, 2, 4]
heap = build_heap_slow(items)
print(heap)  # 輸出: [6, 5, 4, 1, 2, 3]

優化建議

若需高效建堆，推薦使用 Floyd算法（從最后一個非葉子節點開始 heapify_down）：

def build_heap_fast(items):n = len(items)for i in range((n // 2) - 1, -1, -1):  # 從最后一個非葉子節點開始heapify_down(items, n, i)return items

2. Floyd算法（O(n)）

def build_heap_fast(items):heap = list(items)for i in range(len(heap)//2 - 1, -1, -1):heapify_down(heap, len(heap), i)return heap

`build_heap_fast`?操作解析（最大堆示例）

build_heap_fast?使用?Floyd算法?在?O(n)?時間內將無序數組直接構建成堆。其核心思想是：從最后一個非葉子節點開始，向前逐個執行 heapify_down。

分步圖解

假設輸入數組為 [3, 1, 6, 5, 2, 4]，逐步構建最大堆：

Step 1: 初始化

heap = [3, 1, 6, 5, 2, 4]（直接復制原數組）
最后一個非葉子節點的索引：len(heap)//2 - 1 = 2（即節點?6）

Step 2: 從索引 2 開始?`heapify_down`

處理?i=2（節點6）：
- 左子節點?left=2*2+1=5（值4），右子節點?right=2*2+2=6（超出范圍）。
- largest=2（節點6），比較?left(4) > largest(6)？否?→?無需交換。
- 堆保持不變：

         [3, 1, 6, 5, 2, 4]

Step 3: 處理?`i=1`（節點1）

執行?heapify_down(heap, 6, 1)：
- 左子節點?left=3（值5），右子節點?right=4（值2）。
- largest=1（節點1），比較?left(5) > largest(1)?→?largest=left=3。
- 比較?right(2) > largest(5)？否 → 保持?largest=3。
- 交換?heap?和?heap（1 ? 5），數組變為?[3, 5, 6, 1, 2, 4]。
- 繼續檢查?i=3（節點1），但它是葉子節點，終止。
- 堆狀態：

         [3, 5, 6, 1, 2, 4]

Step 4: 處理?`i=0`（節點3）

執行?heapify_down(heap, 6, 0)：
- 左子節點?left=1（值5），右子節點?right=2（值6）。
- largest=0（節點3），比較?left(5) > largest(3)?→?largest=left=1。
- 比較?right(6) > largest(5)?→?largest=right=2。
- 交換?heap?和?heap（3 ? 6），數組變為?[6, 5, 3, 1, 2, 4]。
- 繼續檢查?i=2（節點3）：
  - 左子節點?left=5（值4），右子節點?right=6（超出范圍）。
  - 比較?left(4) > largest(3)?→?largest=left=5。
  - 交換?heap?和?heap（3 ? 4），數組變為?[6, 5, 4, 1, 2, 3]。
- 堆最終狀態：

         [6, 5, 4, 1, 2, 3]

最終堆

數組為 [6, 5, 4, 1, 2, 3]，結構如下：

      [6]         ← 根節點最大/   \[5]    [4]      ← 每個父節點 ≥ 子節點/ \    /
[1][2] [3]

關鍵點總結

時間復雜度：
- O(n)（Floyd算法比逐個插入的 O(n log n) 更高效）。
空間復雜度：
- O(1)（原地修改，無需額外空間）。
為什么從?n//2 -1?開始：
- 葉子節點本身已是合法堆，只需調整非葉子節點。
對比?build_heap_slow：
方法時間復雜度空間復雜度適用場景
build_heap_slow O(n log n) O(n) 動態插入
build_heap_fast O(n) O(1) 靜態數組批量建堆

方法	時間復雜度	空間復雜度	適用場景
`build_heap_slow`	O(n log n)	O(n)	動態插入
`build_heap_fast`	O(n)	O(1)	靜態數組批量建堆

完整代碼示例（最大堆）

def heapify_down(heap, n, i):while True:left = 2 * i + 1right = 2 * i + 2largest = iif left < n and heap[left] > heap[largest]:largest = leftif right < n and heap[right] > heap[largest]:largest = rightif largest != i:heap[i], heap[largest] = heap[largest], heap[i]i = largestelse:breakdef build_heap_fast(items):heap = list(items)for i in range(len(heap) // 2 - 1, -1, -1):  # 從最后一個非葉子節點向前heapify_down(heap, len(heap), i)return heap# 示例用法
items = [3, 1, 6, 5, 2, 4]
heap = build_heap_fast(items)
print(heap)  # 輸出: [6, 5, 4, 1, 2, 3]

Floyd算法數學原理

建堆復雜度證明：
- 第 k 層的節點最多需要下沉?h-k?次（h 是堆高度）。
- 總操作次數 = Σ (節點數 × 下沉次數) = Σ 2? × (h-k) ≈ O(n)。
為什么快：
- 越下層的節點越多，但需要調整的次數越少；越上層的節點越少，但調整次數多。兩者平衡后為線性復雜度。

堆排序

def heap_sort(arr):# 構建最大堆n = len(arr)for i in range(n//2 - 1, -1, -1):heapify_down(arr, n, i)# 逐個提取元素for i in range(n-1, 0, -1):arr[0], arr[i] = arr[i], arr[0]  # 交換根與末尾heapify_down(arr, i, 0)  # 對縮小后的堆進行調整

`heap_sort`?操作解析（升序排序示例）

堆排序分為兩步：

構建最大堆：將無序數組調整為最大堆結構。
逐個提取最大值：將堆頂（最大值）與末尾交換，縮小堆范圍并重新調整。

分步圖解

假設輸入數組為 [3, 1, 6, 5, 2, 4]，逐步進行堆排序：

Step 1: 構建最大堆

調用 build_heap_fast 后，數組變為 [6, 5, 4, 1, 2, 3]，結構如下：

      [6]         ← 根節點最大/   \[5]    [4]/ \    /
[1][2] [3]

Step 2: 排序階段

第一次交換（i=5）：
- 交換?arr?和?arr（6 ? 3），數組變為?[3, 5, 4, 1, 2, 6]。
- 對前 5 個元素?[3, 5, 4, 1, 2]?執行?heapify_down(arr, 5, 0)：
  - 節點?3?與子節點?5?和?4?比較 → 交換?3?和?5?→?[5, 3, 4, 1, 2, 6]。
  - 節點?3?繼續與子節點?1?和?2?比較 → 交換?3?和?2?→?[5, 2, 4, 1, 3, 6]。
- 當前堆范圍?[5, 2, 4, 1, 3]，結構如下：

         [5]/   \[2]   [4]/ \[1][3]

第二次交換（i=4）：
- 交換?arr?和?arr（5 ? 3），數組變為?[3, 2, 4, 1, 5, 6]。
- 對前 4 個元素?[3, 2, 4, 1]?執行?heapify_down(arr, 4, 0)：
  - 節點?3?與子節點?2?和?4?比較 → 交換?3?和?4?→?[4, 2, 3, 1, 5, 6]。
- 當前堆范圍?[4, 2, 3, 1]，結構如下：

         [4]/   \[2]   [3]/[1]

后續交換（i=3, 2, 1）：
- 類似操作，每次交換堆頂和當前末尾，縮小堆范圍并調整。
- 最終數組變為?[1, 2, 3, 4, 5, 6]（升序排列）。

關鍵點總結

時間復雜度：
- 建堆：O(n)。
- 排序階段：共 n-1 次交換和調整，每次調整 O(log n) →?總 O(n log n)。
空間復雜度：
- O(1)（原地排序）。
穩定性：
- 不穩定（交換可能破壞相同元素的相對順序）。
對比其他排序：
排序算法平均時間復雜度空間復雜度穩定性
堆排序 O(n log n) O(1) 不穩定
快速排序 O(n log n) O(log n) 不穩定
歸并排序 O(n log n) O(n) 穩定

排序算法	平均時間復雜度	空間復雜度	穩定性
堆排序	O(n log n)	O(1)	不穩定
快速排序	O(n log n)	O(log n)	不穩定
歸并排序	O(n log n)	O(n)	穩定

完整代碼示例

def heapify_down(arr, n, i):while True:left = 2 * i + 1right = 2 * i + 2largest = iif left < n and arr[left] > arr[largest]:largest = leftif right < n and arr[right] > arr[largest]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]i = largestelse:breakdef heap_sort(arr):n = len(arr)# 構建最大堆for i in range(n//2 - 1, -1, -1):heapify_down(arr, n, i)# 逐個提取最大值for i in range(n-1, 0, -1):arr[0], arr[i] = arr[i], arr[0]  # 交換heapify_down(arr, i, 0)  # 調整縮小后的堆# 示例用法
arr = [3, 1, 6, 5, 2, 4]
heap_sort(arr)
print(arr)  # 輸出: [1, 2, 3, 4, 5, 6]

為什么堆排序不如快速排序常用？

緩存不友好：堆排序的跳躍式訪問（非連續內存）比快速排序的局部訪問慢。
常數因子大：實際運行中，堆排序的常數因子通常比快速排序大。
不穩定：某些場景需要穩定性。

高級堆結構

1. 二項堆

由一組二項樹組成的森林
支持O(1)時間合并

2. 斐波那契堆

理論最優的優先級隊列
插入/合并：O(1)攤還時間
提取最小：O(log n)攤還時間

3. 配對堆

簡單高效的堆結構
實踐表現優于理論復雜度

實際應用場景

1. 優先級隊列

操作系統進程調度
網絡帶寬管理

2. 算法優化

Dijkstra最短路徑算法
Prim最小生成樹算法
Top K問題（前K大/小元素）

3. 事件驅動模擬

離散事件模擬系統
游戲引擎事件處理

4. 實時系統

緊急任務優先處理
醫療監控系統警報

Python中的堆模塊

import heapq  # 最小堆實現nums = [3, 1, 4, 1, 5, 9, 2, 6]
heap = []# 構建堆
for num in nums:heapq.heappush(heap, num)  # [1, 1, 2, 3, 5, 9, 4, 6]# 訪問最小元素
print(heap[0])  # 1 (不彈出)# 彈出最小元素
print(heapq.heappop(heap))  # 1
print(heap)  # [1, 3, 2, 6, 5, 9, 4]# 堆排序
print([heapq.heappop(heap) for _ in range(len(heap))])  # [1, 2, 3, 4, 5, 6, 9]

堆與相關數據結構對比

特性	堆	二叉搜索樹	有序數組
極值訪問	O(1)	O(log n)	O(1)
插入/刪除	O(log n)	O(log n)	O(n)
構建	O(n)	O(n log n)	O(n log n)
空間開銷	O(n)	O(n)	O(n)
部分有序	是	完全有序	完全有序
范圍查詢	不支持	支持	支持