Java数据结构：PriorityQueue堆与优先级队列：从概念到手写大根堆

堆与优先级队列：从概念到手写大根堆（Java）

写算法写到后面，会越来越频繁地遇到一种需求：我不想按进入顺序取数据（FIFO），我想按“重要程度/大小”取。比如任务调度、Dijkstra、Top-K、定时器、甚至游戏里“高优先级事件先处理”。这时候普通队列就不够用了，需要的是优先级队列（Priority Queue）：支持“加入元素”和“取出最高优先级元素”。

而在 Java 里，PriorityQueue的底层结构就是堆。
所以把堆学明白，等于把一大堆“面试/工程常用场景”打通。

1. 堆到底是什么？

堆（Heap）可以理解为：在完全二叉树的形状约束上，再加一条“父子大小关系”的约束。

• 形状约束：堆一定是一棵完全二叉树（从上到下、从左到右尽量填满）。

• 大小约束（二选一）：

  • 大根堆（最大堆）：父节点 ≥ 子节点，堆顶是最大值
  • 小根堆（最小堆）：父节点 ≤ 子节点，堆顶是最小值
    对大小堆的定义就是用这种父子关系不等式来描述的。

这两条约束带来一个“爽点”：

只要维护堆性质，堆顶永远是当前集合的最大/最小值。
这正是优先级队列想要的。

2. 为什么堆适合用数组存？

因为堆是完全二叉树，层序存进数组不会浪费空位（不像普通二叉树会有大量 null 洞）。强调：非完全二叉树不适合顺序存储，会导致空间利用率低。

数组下标和树结构的对应关系（非常重要，写 siftUp/siftDown 全靠它）：

• 下标i的父节点：(i - 1) / 2
• 下标i的左孩子：2*i + 1
• 下标i的右孩子：2*i + 2

在TestHeap里，这些公式被完整用在siftDown和siftUp中：

intchild=2*parents+1;// 左孩子intparent=(child-1)/2;// 父节点

手写堆代码总览如下

packageDataStructure;importjava.util.Arrays;publicclassTestHeap{publicint[]elem;publicintusedSize;publicTestHeap(){this.elem=newint[10];}publicvoidinitElem(int[]array){for(inti=0;i<array.length;i++){this.elem[i]=array[i];this.usedSize++;}}publicvoidcreateHeap(){for(intparents=(this.usedSize-1-1)/2;parents>=0;parents--){//这里解释一下，this.usedSize - 1 代表最后一个子树的下标，再减一除以二就是最后一个子树的——//——双亲节点的下标，这里建大根堆就从下往上开始建siftDown(parents,this.usedSize);}}publicvoidsiftDown(intparents,intusedSize){//自顶向下比较intchild=2*parents+1;while(child<usedSize){//防止数组下标越界，找到左右孩子的最大值if(child+1<usedSize&&elem[child]<elem[child+1]){child++;}if(elem[child]>elem[parents]){// int tmp = elem[child];// elem[child] = elem[parents];// elem[parents] = tmp;swap(elem,child,parents);parents=child;child=2*parents+1;//这两行的意思是，从parents开始向下比较，比完了//child就继续向下加，直到加到usedSize - 1的位置(最后一个元素)，就算比完了}else{break;}}}publicvoidpush(intval){if(isFull()){elem=Arrays.copyOf(elem,2*elem.length);}usedSize++;elem[usedSize-1]=val;siftUp(usedSize-1);}publicvoidsiftUp(intchild){//自底向上比较intparent=(child-1)/2;while(parent>=0){if(elem[child]>elem[parent]){swap(elem,child,parent);child=parent;parent=(child-1)/2;//也是向上走}else{break;}}}publicbooleanisFull(){returnusedSize==elem.length;}publicvoidswap(int[]elem,inti,intj){inttmp=elem[i];elem[i]=elem[j];elem[j]=tmp;}publicintpoll(){if(isEmpty())return-1;intval=elem[0];swap(elem,0,usedSize-1);usedSize--;siftDown(0,usedSize);returnval;}publicbooleanisEmpty(){returnusedSize==0;}publicvoidheapSort(){intend=usedSize-1;while(end>0){swap(elem,0,end);siftDown(0,end);end--;}}}

3. 手写堆的“骨架”：elem + usedSize

这份实现的整体结构很典型：

publicint[]elem;// 数组存堆publicintusedSize;// 当前有效元素个数（堆大小）

• elem是存储区
• usedSize是“堆里目前有多少元素”
• 空间不足时扩容：Arrays.copyOf（这和 JDK 的PriorityQueue自动扩容思想一致，只是扩容倍率细节不同）

4. 堆的灵魂操作 ①：向下调整 siftDown（建堆、删除都靠它）

4.1 siftDown 在解决什么问题？

当某个节点（通常是 parent）可能比孩子小（大根堆场景），就需要把它往下“沉”，直到父子关系恢复正确。

对“向下调整”的描述很标准：从 parent 出发，比较左右孩子，选择更合适的那个孩子交换，继续向下。并且提醒了一个关键前提：要向下调整 parent，必须保证它的左右子树已经是堆。

4.2 这份 siftDown 的细节（大根堆版本）

核心逻辑非常清晰：

1. child先指向左孩子
2. 如果右孩子存在，挑左右孩子中更大的那个（大根堆就挑大的）
3. 如果孩子比父大，就交换并继续向下
4. 否则 break（说明这棵子树已经满足堆性质）

代码对应：

intchild=2*parents+1;while(child<usedSize){if(child+1<usedSize&&elem[child]<elem[child+1]){child++;}if(elem[child]>elem[parents]){swap(elem,child,parents);parents=child;child=2*parents+1;}else{break;}}

这个写法的好处是：每次只沿着一条路径下沉，最多下沉到叶子，时间复杂度就是树高O(log n)

5. 堆的创建 createHeap：为什么从最后一个非叶子开始？

createHeap()这段是自底向上的建堆：

for(intparents=(this.usedSize-1-1)/2;parents>=0;parents--){siftDown(parents,this.usedSize);}

这里(usedSize - 2) / 2就是“最后一个非叶子节点”的下标——因为叶子节点根本没有孩子，不需要下沉。

自底向上建堆的关键直觉是：

• 最底层的叶子天然是堆
• 往上一层，每个 parent 的左右子树都已经是堆，于是可以安全siftDown(parent)
  这正好吻合“向下调整的前提”。

建堆复杂度也很常被问：并不是n log n，而是O(n)（教材/课件通常会用满二叉树分层求和证明）。

一句话记忆：建堆看起来像“很多次 log”，但下层节点下沉高度很小，摊还下来是 O(n)。

6. 堆的灵魂操作 ②：向上调整 siftUp（插入靠它）

插入（push）的两步非常固定：
先把新元素放到底层最后，再向上调整恢复堆性质。

这份实现对应：

publicvoidpush(intval){if(isFull()){elem=Arrays.copyOf(elem,2*elem.length);}usedSize++;elem[usedSize-1]=val;siftUp(usedSize-1);}

siftUp的思想是“冒泡上浮”：

• child 找 parent
• 如果 child 比 parent 大（大根堆），交换
• child 指向 parent，继续向上

intparent=(child-1)/2;while(parent>=0){if(elem[child]>elem[parent]){swap(elem,child,parent);child=parent;parent=(child-1)/2;}else{break;}}

这里我会做一个“工程味的小提醒”：更常见的循环条件是while(child > 0)，语义更直观；现在用parent >= 0也能跑通（因为 child=0 时 parent=0，会立即 break），只是读起来稍绕一点。

插入的时间复杂度是O(log n)（上浮最多走树高）。

7. 删除堆顶 poll：堆删除永远删的是“堆顶”

堆的删除非常有仪式感：只能删除堆顶（因为堆顶代表“最高优先级”）。
1）堆顶与最后一个元素交换
2）有效元素个数减一
3）对堆顶做向下调整恢复堆性质

这份实现一一对应：

publicintpoll(){if(isEmpty())return-1;intval=elem[0];swap(elem,0,usedSize-1);usedSize--;siftDown(0,usedSize);returnval;}

这就是优先级队列的poll()的本质：取最高优先级（大根堆取最大，小根堆取最小），并维护结构仍然是堆。

8. 堆排序 heapSort：用“反复删除堆顶”来排序

1. 建堆

   • 想要升序：建大堆（最大值不断放到数组末尾）
   • 想要降序：建小堆

2. 利用删除思想排序

   • 把堆顶（最大）与末尾交换
   • “堆大小”缩小 1
   • 对堆顶向下调整

这份heapSort()就是标准的大根堆升序写法：

intend=usedSize-1;while(end>0){swap(elem,0,end);siftDown(0,end);// 注意：end 作为“新的堆大小”（右边已排序区不再参与）end--;}

排序完成后，数组就是升序排列。整体复杂度O(n log n)，额外空间O(1)（原地排序）。

9. 和 Java PriorityQueue 对照一下：默认小根堆，想要大根堆要比较器

对PriorityQueue的注意事项：

• 元素必须可比较，否则会ClassCastException
• 不能插入null，否则NullPointerException
• 默认是小根堆
• 插入/删除的时间复杂度是对数级（本质就是 siftUp/siftDown）
• 扩容会带来拷贝成本，最好在已知规模时给个初始容量（课件还给了 JDK1.8 的扩容策略示例）

想要“大根堆”，就是提供Comparator反转比较顺序——这和最小 K 个数那题里“用大根堆维护 k 个候选”的做法完全一致。

10. 堆的一个杀手级应用：Top-K（最小 K / 最大 K）

拿 Top-K 做总结：数据量大时不适合直接排序，堆是最佳方案之一。思路也很固定：

• 求前 K 个最小：维护一个大小为 K 的大根堆（堆顶是“当前最差/最大”的那个）
• 求前 K 个最大：维护一个大小为 K 的小根堆

遍历剩余元素，与堆顶比较，合格就替换堆顶。最后堆里剩下的就是答案。

11. 这份手写堆实现的小结与几个“实战建议”

这份TestHeap把堆的四件核心事都打通了：

• 建堆：createHeap()+siftDown()
• 插入：push()+siftUp()
• 删除堆顶：poll()+siftDown()
• 堆排序：heapSort()（反复 swap + 下沉）

如果把它当作“可复用的工程组件”，我通常会额外加几条强化：

1. initElem前先确保容量足够（数组长度可能 > 10，需要扩容或直接copyOf）
2. poll()空堆返回-1适合演示；工程里更常见的是抛异常或返回OptionalInt
3. 把Stack/Vector这类老容器替换为更现代的结构（这里已经用数组实现了核心，不受影响）

最后用一句话把堆记牢

堆是“完全二叉树 + 父子有序”，用数组存；真正维护它的只有两招：向下调整和向上调整。
把这两招写对，优先级队列、堆排序、Top-K 这些题基本就不怕了。