數據結構專欄 ?(click)

---

今天就讓我們來聊聊這個讓無數程序員又愛又恨的數據結構——堆（Heap）。

一、優先級隊列 vs 普通隊列

特性	普通隊列	優先級隊列
出隊順序	FIFO（先進先出）	按優先級高低（默認小的先出）
底層實現	數組/鏈表	通常用堆實現
時間復雜度	O(1)	插入O(logN)，刪除O(logN)
Java實現	Queue接口	PriorityQueue類
典型應用場景	消息隊列、BFS算法	任務調度、TopK問題

二、堆：一棵"偏心的"完全二叉樹

堆的類型對比

類型	特點	應用場景
大根堆	父節點 ≥ 子節點	堆排序（升序）、TopK最小
小根堆	父節點 ≤ 子節點	堆排序（降序）、TopK最大
二叉堆	完全二叉樹實現，常用數組存儲	最常用實現
斐波那契堆	更優的理論時間復雜度，但實現復雜	圖算法優化

// 堆的數組表示
parent(i) = (i-1)/2  // 找父節點
left(i) = 2*i + 1    // 左孩子
right(i) = 2*i + 2    // 右孩子

三、堆的核心操作：上下調整

操作復雜度對比

操作	時間復雜度	空間復雜度	說明
插入(offer)	O(logN)	O(1)	需要向上調整(shiftUp)
刪除(poll)	O(logN)	O(1)	需要向下調整(shiftDown)
查看(peek)	O(1)	O(1)	直接返回堆頂元素
建堆	O(N)	O(1)	自底向上調整比逐個插入更高效

// 向下調整示例（小根堆）
void shiftDown(int[] arr, int parent, int len) {int child = 2*parent + 1;while (child < len) {// 找出較小的孩子if (child+1 < len && arr[child+1] < arr[child]) child++;// 如果父節點已經比孩子小，調整結束if (arr[parent] <= arr[child]) break;swap(arr, parent, child);  // 交換父子parent = child;            // 繼續向下調整child = 2*parent + 1;}
}

四、堆排序 vs 快速排序

特性	堆排序	快速排序
時間復雜度	O(NlogN)	O(NlogN)平均
空間復雜度	O(1)	O(logN)遞歸棧
穩定性	不穩定	不穩定
最壞情況	O(NlogN)	O(N2)
數據訪問模式	跳躍訪問（緩存不友好）	順序訪問（緩存友好）
適用場景	大數據量	中小數據量

五、PriorityQueue使用指南

構造方法對比

構造方法	說明
new PriorityQueue<>()	默認容量11，自然排序
new PriorityQueue<>(int capacity)	指定初始容量
new PriorityQueue<>(Comparator)	自定義比較器（可實現大根堆）
new PriorityQueue<>(Collection)	用已有集合初始化（自動建堆）

// 大根堆實現
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b-a);// 自定義對象排序
PriorityQueue<Student> pq = new PriorityQueue<>((s1, s2) -> s1.score != s2.score ? s2.score - s1.score :  // 分數高的在前s1.name.compareTo(s2.name)  // 分數相同按名字
);

六、TopK問題的三種解法對比

方法	時間復雜度	空間復雜度	適用場景
快速排序+取前K	O(NlogN)	O(logN)	數據可全部裝入內存
堆排序	O(NlogK)	O(K)	海量數據，K較小
冒泡K次	O(N*K)	O(1)	K非常小（如K=1,2）

七、堆的常見面試題

1. 堆的建立過程（以小根堆為例）

//向下調整方法(復雜度logN)public static void shiftDown(int[] array, int index){//要調整的父節點int parent = index;//要調整的孩子節點int child = 2*parent + 1;while (child < array.length){//child+1其實代表的是右子樹//判斷左右子樹大小if(child+1<array.length && array[child+1] < array[child]){//左右子樹對調child = child+1;}//判斷左子樹和父節點的大小if (array[child] >= array[parent]){break;}else{int temp = array[parent];array[parent] = array[child];array[child] = temp;//更新父節點和子節點的指向parent = child;child = 2*parent +1;}}}/***建堆操作復雜度O(n)* @param array*/public static void createHeap(int[] array){//要先找到最后一個非葉子節點int lastLeaf  = array.length-1;int lastParent = (lastLeaf-1)/2;for (int i = lastParent; i >= 0; i--){shiftDown(array, i);}}

2. 堆的應用場景總結

應用場景	使用的堆類型	原因說明
堆排序	大根堆/小根堆	升序用大根堆，降序用小根堆
TopK最大元素	小根堆	維護K個元素的小根堆，淘汰小的
TopK最小元素	大根堆	維護K個元素的大根堆，淘汰大的
任務調度（優先級高的先執行）	大根堆	優先級高的在堆頂
合并K個有序鏈表	小根堆	每次取最小節點，效率O(logK)
Dijkstra算法	小根堆	每次取距離最小的節點

八、總結：堆的"堆"德

堆的優缺點分析

優點：

1. 插入/刪除時間復雜度穩定在O(logN)
2. 獲取極值（堆頂）只需O(1)
3. 可以高效解決TopK問題
4. 堆排序是原地排序，空間復雜度O(1)

缺點：

1. 訪問非堆頂元素效率低（需要遍歷）
2. 不是穩定排序（相同元素可能換位）
3. 緩存不友好（數組跳躍訪問）

九、終極對比表：堆 vs 其他數據結構

特性	堆	二叉搜索樹	跳表	哈希表
查找極值	O(1)	O(logN)	O(logN)	O(N)
插入/刪除	O(logN)	O(logN)	O(logN)	O(1)平均
有序性	部分有序（僅堆頂）	完全有序	完全有序	無序
空間復雜度	O(N)	O(N)	O(N)	O(N)
實現難度	中等	中等	困難	中等
典型應用	優先級隊列、TopK	范圍查詢、有序數據	高性能有序數據結構	快速查找、去重

---

最后的小幽默：

程序員的世界里：

• 當你學會堆：哇！我"堆"數據結構理解好深！
• 當你寫堆代碼：這bug怎么"堆"了這么多！
• 當你面試被問堆：面試官，咱們能"堆"心一點嗎？