在上一篇二叉树学习笔记中我们认识了完全二叉树而堆正是完全二叉树最经典的应用之一。日常Java开发里PriorityQueue底层就是堆结构。不管是笔试OJ、算法面试堆都是高频考点堆排序、Top-k问题更是常客。本篇结合学习大纲基于Java的视角梳理堆的整套知识体系。堆本质是满足堆性质的完全二叉树分为大根堆和小根堆大根堆父节点大于等于子节点堆顶是最大值小根堆父节点小于等于子节点堆顶是最小值。依托完全二叉树的特点堆采用数组顺序存储不需要像普通二叉树那样用链表节点。通过下标就能快速定位父子节点下标i的节点左孩子2*i1右孩子2*i2父节点(i-1)/2这是堆所有操作的底层基础。堆的核心是**向下调整**与**向上调整**两个算法也是我们手写堆必须掌握的逻辑。向下调整的前提是左右子树已经满足堆的性质只需要把当前节点向下交换下沉到合适位置。建堆操作就是从最后一个非叶子节点向前遍历逐个执行向下调整。这里有一个易踩坑知识点批量向下调整建堆时间复杂度是O(n)如果逐个插入元素、靠向上调整建堆时间复杂度是O(nlogn)。 堆的插入和删除逻辑在Java手写实现里很固定。插入时新元素加到数组末尾执行向上调整不断和父节点比较上浮删除一般只删除堆顶元素做法是堆顶和末尾元素交换有效长度减一再对新堆顶做向下调整。堆不适合随机删除中间元素这是它本身的特性。堆最典型的封装就是优先队列。普通队列先进先出优先队列按照优先级出队。Java中提供了PriorityQueue它默认是**小根堆**如果想要大根堆需要传入比较器Comparator.reverseOrder()。我们要熟悉它的常用接口offer()入队、poll()取出堆顶、peek()查看堆顶、isEmpty()判空。吃透API之后配合OJ练习熟悉优先队列的题型套路比如任务调度、多路归并问题。堆的三大经典应用也是Java算法练习的重点手写实现优先队列、堆排序、Top-k问题。 堆排序升序排序一般构建大根堆。循环将堆顶最大值和当前末尾元素交换再对剩余区间向下调整逐步把最大值放到数组尾部。堆排序时间复杂度稳定O(nlogn)原地排序空间复杂度低缺点是属于不稳定排序。 Top-k问题是面试热门在大量数据中找出前K大或者前K小的数。如果数据量很大全部排序开销很高。Java里标准解法找前K大元素维护一个容量为K的小根堆遍历全部数字当元素比堆顶大就弹出堆顶、加入新元素。遍历完成后堆中就是最大的K个元素。这个方案优势是内存可控适合海量数据流场景。 掌握堆之后我们不仅能搞定算法题也能理解Java集合中优先队列的底层逻辑为后续学习高级算法打下基础。