今天我学习了堆的核心操作对堆这个数据结构有了更深刻的理解。特此写一篇博客加深印象希望也能帮助到正在学习的朋友们。一、什么是堆堆是一种完全二叉树并且满足以下性质大根堆Max Heap每个节点的值 ≥ 其子节点的值即根节点是最大值小根堆Min Heap每个节点的值 ≤ 其子节点的值即根节点是最小值堆通常用数组存储无需指针。根节点下标为 0对于下标为 i 的节点左孩子下标 2*i 1 右孩子下标 2*i 2 父节点下标 (i - 1) / 2二、堆的存储结构MyHeap大根堆的底层是一个int[] elem数组加上一个usedSize记录元素个数publicclassMyHeap{publicint[]elem;// 底层数组publicintusedSize;// 当前堆中元素个数publicMyHeap(){this.elemnewint[10];// 默认容量}publicvoidinit(int[]arr){this.elemArrays.copyOf(arr,arr.length);usedSizethis.elem.length;}}三、核心操作1. 向下调整Sift Down向下调整Sift Down是堆中删除堆顶和建堆时使用的核心操作。当堆顶元素被移除或建堆时从某个父节点出发该位置可能不再满足堆性质大根堆中父节点 ≥ 子节点。向下调整的思路是从当前父节点出发先找出左右孩子中较大的那个然后与父节点比较——如果孩子比父节点大就交换两者父节点下沉到孩子的位置继续向下比较直到到达叶子节点或满足堆性质为止。这个过程就像较大的元素不断「下沉」到合适的位置因此得名「向下调整」。删除堆顶或建堆时使用。将 parent 位置的元素与较大的孩子交换直到满足堆性质。privatevoidsiftDown(intparent,intusedSize){intchildparent*21;// 左孩子while(childusedSize){// 选出左右孩子中较大的那个if(child1usedSizeelem[child]elem[child1]){child;}// 孩子比父亲大交换并继续向下if(elem[child]elem[parent]){swap(elem,child,parent);parentchild;childparent*21;}else{break;// 已满足堆性质}}}2. 向上调整Sift Up向上调整Sift Up是堆中插入元素时使用的核心操作。当新元素被添加到数组末尾时它可能破坏堆的性质大根堆中父节点 ≥ 子节点。向上调整的思路是从新元素的位置出发不断与它的父节点比较——如果当前节点比父节点大就交换两者然后继续向上比较直到到达根节点或满足堆性质为止。这个过程就像气泡从底部向上浮动因此得名「向上调整」。插入元素时使用。将新元素放到数组末尾然后不断与父节点比较并交换。privatevoidsiftUp(intchild){intparent(child-1)/2;while(child0){if(elem[child]elem[parent]){swap(elem,child,parent);childparent;parent(child-1)/2;}else{break;}}}3. 建堆Heapify从最后一个非叶子节点开始依次向下调整。时间复杂度O(n)。publicvoidcreateHeap(){for(intparent(usedSize-1-1)/2;parent0;parent--){siftDown(parent,usedSize);}}最后一个非叶子节点的下标推导最后一个节点下标为usedSize - 1其父节点为(usedSize - 1 - 1) / 2。4. 插入offerpublicvoidoffer(inta){if(isFull()){elemArrays.copyOf(elem,elem.length*2);// 扩容}elem[usedSize]a;// 放到末尾usedSize;siftUp(usedSize-1);// 向上调整}5. 删除堆顶pollpublicintpoll(){if(isEmpty())return-1;intretelem[0];// 保存堆顶swap(elem,0,usedSize-1);// 堆顶与末尾交换usedSize--;// 逻辑删除siftDown(0,usedSize);// 新堆顶向下调整returnret;}四、Java PriorityQueueJDK 自带的堆实际开发中很少手写堆Java 提供了PriorityQueue底层就是小根堆默认基于Object[]数组实现自动扩容。基本操作// 创建小根堆默认PriorityQueueIntegerminHeapnewPriorityQueue();// 创建大根堆PriorityQueueIntegermaxHeapnewPriorityQueue((a,b)-b-a);// 常见操作minHeap.offer(3);// 插入O(log n)minHeap.offer(1);minHeap.offer(2);minHeap.peek();// 取堆顶最小值不删除 → 1minHeap.poll();// 删除堆顶并返回 → 1O(log n)minHeap.size();// 堆中元素个数minHeap.isEmpty();// 是否为空PriorityQueue 与手写堆的对比对比项MyHeap手写PriorityQueue默认类型大根堆小根堆改大/小根堆改比较符号传 Comparator底层int[]Object[] 泛型扩容手动写自动扩容堆排序手写循环逐个 poll 即可适用场景面试手撕、理解原理实际开发、竞赛用 PriorityQueue 实现 Top Kpublicint[]topK(int[]arr,intk){if(k0)returnnewint[0];// 小根堆堆顶是 k 个数中最小的PriorityQueueIntegerpqnewPriorityQueue();// 默认小根堆for(intx:arr){pq.offer(x);if(pq.size()k)pq.poll();// 超过 k 就弹走最小的}int[]resnewint[k];for(intik-1;i0;i--){res[i]pq.poll();// 从后往前填得到升序结果}returnres;}三行核心逻辑比手写堆简洁得多。PriorityQueue 的注意事项不允许 null会抛 NPE线程不安全多线程用PriorityBlockingQueue迭代器不保证顺序想有序输出必须逐个 poll对象元素需实现Comparable或传入Comparator否则运行时抛 ClassCastException五、复杂度总结操作手写堆 / PriorityQueue建堆O(n)插入 offerO(log n)删除堆顶 pollO(log n)取堆顶 peekO(1)六、堆排序利用大根堆进行原地升序排序publicvoidheapSort(){intendusedSize-1;while(end0){swap(elem,0,end);// 堆顶最大值放到末尾siftDown(0,end);// 剩余部分调整为大根堆end--;}}步骤先建大根堆createHeap依次将堆顶与末尾交换交换后向下调整每次将当前最大值放到数组尾部最后得到升序数组七、Top K 问题找数组中最小的 k 个数可以用一个大小为 k 的大根堆publicint[]topK(int[]arr,intk){if(k0)returnnewint[0];MyHeapheapnewMyHeap();for(inti0;ik;i){heap.offer(arr[i]);// 先入 k 个}for(intik;iarr.length;i){if(arr[i]heap.peek()){// 比堆顶小才入堆heap.poll();heap.offer(arr[i]);}}int[]resnewint[k];for(intik-1;i0;i--){res[i]heap.poll();}returnres;}核心思想大根堆堆顶是 k 个数中最大的遍历数组时只替换比堆顶小的数最终堆里留下的就是最小的 k 个。时间复杂度 O(n log k)。八、应用场景优先队列操作系统任务调度、Dijkstra 最短路径Top K 问题最小的 k 个数、最大的 k 个数数据流中位数一个大根堆 一个小根堆合并 K 个有序链表将链表头节点入小根堆每次弹出最小节点定时器任务调度按触发时间堆排序每次取最近的任务九、总结概念要点存储结构数组完全二叉树两个核心操作向上调整 siftUp插入、向下调整 siftDown删除/建堆建堆从下往上 siftDownO(n)典型应用堆排序、Top K、优先队列手写堆的关键就是理解 siftUp 和 siftDown 这两个方法剩下的插入、删除、建堆、排序都是对它们的组合调用。十、感悟——学习堆的感悟学习堆这个数据结构让我对「数据结构是算法的基石」这句话有了更深的体会。以下是我的一些感悟从抽象到具体堆的概念完全二叉树 父节点与子节点的大小关系听起来很抽象但一旦用数组实现就变得非常具体。下标公式2*i1、(i-1)/2就像一把钥匙把树形结构映射到了线性存储上。两个核心操作贯穿始终siftDown 和 siftUp 就像堆的「呼吸」——建堆、删除用 siftDown插入用 siftUp。理解了这两个方法剩下的插入、删除、建堆、排序都只是它们的组合调用一通百通。O(n) 建堆的巧妙从最后一个非叶子节点开始向下调整时间复杂度居然是 O(n) 而不是 O(n log n)这个结论第一次看到时让我很惊讶。仔细推导后发现越底层的节点数量越多但调整次数越少这种「多数节点少干活」的设计非常精妙。对比学习加深理解手写 MyHeap 后再用 Java 的 PriorityQueue能更清楚地看到 JDK 帮我们封装了什么自动扩容、泛型、Comparator也更能体会「轮子」背后的原理。应用驱动学习Top K、堆排序、数据流中位数……这些经典问题让我看到堆不只是面试题而是真实世界中解决「优先级」「最值」「排序」问题的利器。总的来说堆是一个「代码量不大但思想很丰富」的数据结构。花时间手写一遍、画图模拟调整过程远比死记硬背代码有效。希望这篇博客也能帮你真正理解堆。
