提到“堆”很多开发者的第一反应是同一个词劈成两个概念数据结构课本里那棵完全二叉树和程序运行时到处 new 对象的内存区域。这两个概念都叫 heap含义却完全不同。面试时被问“用数组实现一个堆”考察的是数据结构层面的存储设计而服务器上看到 java.lang.OutOfMemoryError: Java heap space调 -Xms/-Xmx又是内存管理层面的事。这篇文章我把这两个维度放在一起讲透。第一堆作为数据结构为什么天生适合用数组存储下标关系怎么推导第二堆在工程运行时到底占哪块内存编译器报堆空间不足、进程堆调到 8000 还是炸应该从哪下手排查。你把这两条线串起来之后“堆的基本存储”就不再是个模糊的问题了。1. 堆逻辑上是树存储上是数组1.1 完全二叉树的“紧凑布局”决定了存储方式先明确一个基础认知堆本质上是一棵完全二叉树。所谓完全二叉树指的是除最后一层外每一层都填满最后一层的节点全部从左向右排列不允许中间空位。打个比方就像往墙角堆放正方体小木块规则是必须先把上一层放满再往下一层的左边依次堆堆到一半就停这就是完全二叉树的形状如果你在第二层中间留个坑把木块放到第三层那就成了普通二叉树完全二叉树那种“可以按序号连续编号”的性质就没了。这个“完整且靠左”的约束看着不起眼实际上等于给存储方案画好了边界树的结构足够规则可以使用数组按层序遍历编号存放不需要额外保存左右孩子指针。指针不是不可以但既然父子关系能够靠下标唯一推导出来再额外存指针就是在浪费内存。对需要处理百万级节点、甚至上 GB 数据的堆来说这种浪费相当可观。底层数据结构的设计通常就是在空间和可推导性之间做取舍堆选择数组本质原因就是“结构太规整不需要指针”。1.2 数组映射背后的唯一性很多人第一次接触堆的数组实现时最不适应的就是“树节点去哪了指针呢”这里有个关键概念一棵完全二叉树可以被层序遍历编号每个节点对应一个确定的下标反过来任何一个合法的下标也一定能映射回树中唯一的一个节点。这种一一对应关系就是数组存储能够成立的基础。我打个比方就像电影院的座位从门口开始按排编号。票上写“7 号座”你不需要看地图走过去数到 7 就能坐下。下标就是座位号数组就是那一排排座位。你问“7 号座的父母坐哪”只需要一个固定公式不需要问工作人员。堆的父子关系也是用公式推导的后面我会把推导过程完整写出来。也必须承认这种映射能成立是有前提的。除了完全二叉树约束外还要规定同一层节点从左到右顺序严格固定不能调换。一旦调换编号体系就乱了数组存储也随之失效。堆在逻辑上是“半有序”的只保证父子之间有顺序约束不保证兄弟之间有序。这个“半有序”恰恰是它能在 O(log n) 时间内完成插入和删除的关键。2. 数组存储的核心细节下标推导公式全解析2.1 从 0 开始的下标约定这是 C、C、Java、Python 等主流语言最常用的约定。假设数组从下标 0 存放堆顶元素那么对任意下标 i 的节点一共需要三个公式左孩子left 2 * i 1右孩子right 2 * i 2父节点parent (i - 1) / 2代入验证一下。堆顶下标 0左孩子是 1右孩子是 2下标 1 的父节点是 (1-1)/20下标 2 的父节点也是 (2-1)/20。下标为 3 的节点父节点是 (3-1)/21下标为 4 的节点父节点是 (4-1)/21。这样每一条父子连线都有唯一的公式支撑。我在笔试里经常看到有人把公式记错尤其右孩子写成 2*i1。最不容易错的记忆方法是把两个孩子看作“从 i 往后延伸的两个相邻位置”左孩子是 i 后面的第一个右孩子紧挨着它所以是 2i1 和 2i2。这不是死记硬背而是完全二叉树的层序编号规律决定的。与之对立的另一种常见约定是从 1 开始编号下面单独讲。2.2 从 1 开始的下标约定有些教材和竞赛题实现堆时会故意把数组下标 0 空出来让真正的堆元素从下标 1 开始。这时三个公式变成左孩子left 2 * i右孩子right 2 * i 1父节点parent i / 2直观程度完全不同。堆顶下标 1左孩子 2右孩子 3下标 2 的父节点是 2/21下标 3 的父节点是 3/21。整数除法直接把父节点算出来不用带任何减号。这就是为什么 C 的 priority_queue 底层默认大根堆、很多线段树风格的模板也喜欢用 1 下标数组。先申请一个长度为 n1 的数组index 0 空着或放哨兵后面所有操作都清爽。从 1 开始还有一个额外好处left2i 写成位运算就是 i 1right2i1 可以写成 (i 1) | 1parenti/2 可以写成 i 1。在追求极致性能的代码里这组位运算很常见而且不容易写错。对于刷题选手来说手写堆用 1 下标版本边界判断会少一些。2.3 为什么两种约定并存两种约定并存不是谁对谁错而是习惯和取舍的混合产物。从 0 出发是大部分语言的天然数组语义直接遍历、扩容时不用特殊处理首元素从 1 出发则公式更干净手写堆时心智负担更小。我自己写代码有个习惯手写轮子时默认用 1 下标版本工程里直接用现成容器则用 0 下标封一层辅助函数。没有任何强制要求但核心原则只有一个选定一种约定后全篇保持一致不要在同一个文件里一半用 0、一半用 1。曾有同事混合用两种下标推导写出来的堆在特定数据规模下表现诡异定位了半天才发现是父节点找到了错误的位置。下标约定这种基础形式一旦混乱排查成本极高。3. 配合数组存储的堆操作上滤与下滤的完整过程3.1 插入元素尾部追加 向上调整堆元素存进数组后插入操作可以概括为“先放到最后再往上爬”。具体过程是把新元素追加到数组末尾此时它暂时处于完全二叉树的最右位置很可能违反堆序然后比较新元素和它的父节点如果新元素更大以大根堆为例下同就交换接着继续向上和新的父节点比较直到它不大于父节点或者走到根节点为止。向上调整因为方向是从下往上通常叫上滤。每次交换只涉及父子两代每一步比较都能确定新元素往上走一层最坏情况是从叶子走到根层数是 log n所以插入时间复杂度是 O(log n)。这个过程不需要申请新节点也不需要整体搬移数组元素就地把最后一位当作新叶子。这也是数组存储的第二个好处追加元素和交换元素都是 O(1) 操作循环比较才是唯一开销。实际编码时我建议把“比较大小”抽象成函数不要在主循环里到处写大于号、小于号。你永远不知道三个月后的自己会不会需要把大根堆改成小根堆一个 comparator 能解决的事别拆成十处维护。同理交换元素也可以抽成一个私有方法避免下滤循环里反复写三行 swap代码可读性会高很多。3.2 删除堆顶尾部补位 向下调整堆最常用的操作是取最值删除堆顶是核心场景。标准流程是先用数组最后一个元素覆盖根节点再让数组逻辑长度减一然后从根节点开始向下调整比较当前节点和左右孩子选出“更大的孩子”大根堆如果孩子更大就交换交换后在新位置继续向下比较。向下调整也叫下滤和插入的上滤形成对称插入是往上爬删除是往下沉。时间复杂度同样是 O(log n)因为每次只下沉一层路径受树高限制。这里有个细节容易踩坑根节点被最后一个元素覆盖后旧堆顶在数组中已经不存在了但物理数组尾部还留着最后的旧值。如果之后遍历数组不区分 size 和 capacity可能把“已删除元素”当有效数据带出来。用动态数组实现时循环边界和实际数据量一定要以 size 为准而不是以数组长度为准。3.3 原地建堆从最后一个非叶子节点开始给定一组无序数组要在 O(n) 时间内原地把它调整成堆标准的做法是自底向上的逐节点下滤。先要找到最后一个非叶子节点对 0 下标数组它是 n/2 - 1对 1 下标数组它是 n/2。从这个节点开始递减到根节点对每个节点执行一次向下调整。为什么起点是中间而不是末尾因为从 n/2 往后的节点全是叶子节点。单独的叶子天然满足堆序不需要调整。从最后一个非叶子节点开始能够保证每次处理节点时它的左右子树已经是合法的堆下滤一次就能让整棵子树满足堆序。这个顺序是自底向下的和递归里“先处理子树再处理本身”的思路一致。很多人觉得原地建堆是 O(n log n)因为它看起来对 n 个节点各做了 O(log n) 的下滤。实际算下来是 O(n)原因也不复杂越靠近树底的节点数量越多但它们能下沉的深度越浅越靠近根部的节点数量少却拥有更深的下降路径但数量又很少。把每一层的工作量按等比数列求和结果收敛到线性。这是堆里最经典的复杂度结论之一面试也常考。3.4 复杂度分析为什么堆操作都围绕 O(log n)可以牢记一个思维模型无论上滤还是下滤一次循环处理一层。完全二叉树的高度是 O(log n)所以插入、删除堆顶、调整单个节点都是 O(log n)。而建堆因为每个节点最多被处理一次工作量沿深度分层求和才是 O(n)。数组存储没有改变这些复杂度但让复杂度保持得很干净这得益于数组的 O(1) 随机访问。链式二叉树要做同样的上滤得从叶子往父节点跳父指针本身就是额外内存储开销更麻烦的是缓存不友好访问一个节点后它的孩子大概率不在相邻地址每次都要打一次内存。数组实现里父子节点间距分别是 1、2、3 这样的小数字完全可以把一个连续区域的访问命中在 CPU 缓存里。数据量一大这个差距会放大得非常明显这也是我倾向于在工程里用数组堆而不是链式堆的核心原因。4. 工程中的“堆存储”内存堆、编译器报错与栈溢出4.1 运行时数据区里的堆长什么样工程里的“堆”和数据结构里的“堆”差着一层。程序运行时的堆属于内存管理范畴。拿 Java 虚拟机举例运行时数据区里有一块被所有线程共享的堆区new 出来的对象、数组绝大多数都在这里分配由垃圾收集器自动回收。启动参数 -Xms 指定初始大小-Xmx 指定最大大小。当堆空间耗尽且 GC 无法回收出足够空间时就会抛出 java.lang.OutOfMemoryError: Java heap space。很多初学者在这里被绕晕代码里写了一个 PriorityQueue底层用数组实现这个数组在 JVM 里也是对象也分配在内存堆区。所以“数据结构堆”和“内存管理堆”其实是两层概念。外层是 JVM 给所有动态对象分配的共享区域内层是我们的堆结构自己管理的元素数组。结构堆决定数据用什么形式组织内存堆决定数据放在哪块空间两者各司其职别混为一谈。4.2 编译/构建时“堆空间不足”的排查思路提到 OOM 报错很多人第一反应是运行时服务器内存不够。但编译阶段也会看到类似错误。比如在 IDEA 里跑一个大型项目控制台输出 java.lang.OutOfMemoryError: GC overhead limit exceeded这时通常不是业务代码的问题而是编译器进程自身的堆空间不够。IDEA 的编译器进程堆大小默认并不大几百 MB 是很常见的。遇到大型 Android 项目、Kotlin 项目或多模块 Maven 项目时确实不够用。常规解法是在 Settings 里找到 Compiler把 Shared build process heap size 调大比如 1500MB。命令行方式则是在启动脚本里设置 MAVEN_OPTS 或 JAVA_OPTS给 Maven 使用的 JVM 扩堆。Kotlin 编译慢或内存不足时还要单独调 kotlin.daemon.jvmargs 参数。有一种反直觉的情况你把进程堆大小调整到 8000MB甚至更多还是不断报 OOM。这往往说明问题不在堆的总量上。最常见的原因是内存泄漏对象被某些容器长期引用无法回收堆被一点一点填满其次是某个超大对象或多个大量重复对象把空间瞬间撑爆还有一种可能是 MetaSpace 存不下加载进来的类定义。调整 -Xmx 是治标找到根因才是治本。我之前处理过一个案例问题出在缓存 key 无限增长把整块堆消耗殆尽单纯加大堆上限只是晚一点崩。4.3 堆外内存堆里存不下还能存哪JVM 里还有一块内存不归堆管理叫堆外内存。最典型的是 NIO 的 DirectByteBuffer通过 ByteBuffer.allocateDirect 申请的内存由操作系统直接分配不经过垃圾回收器管理。它的优势是能绕开 JVM 堆与内核之间的一次拷贝在 IO 密集场景明显提升吞吐代价是回收时机不受 GC 控制用完后必须显式释放否则会持续占用操作系统内存。-XX:MaxDirectMemorySize 参数限制堆外内存总量默认情况下等于 -Xmx 的大小。很多 Netty 应用出现“总内存看着涨、堆却一直正常”的谜案最后基本都落在 Direct Memory 没有及时释放上。排查时可以借助 native memory tracking命令是 jcmd VM.native_memory summary它会按 Java Heap、Class、Thread、GC、Compiler、Native 等分类统计内存占用。先看哪一块异常增长再对症下药比自己瞎猜高效得多。4.4 别把栈溢出和堆溢出搞混堆溢出讲完栈溢出是另一个高频报错。StackOverflowError 通常来自方法调用太深最常见的是递归没有终止条件或者递归深度超过默认栈容量。栈是每线程私有的存放局部变量、方法调用帧和返回地址。Java 线程栈默认大小约 1MB用 -Xss 可以调大但调大线程栈会加重内存压力毕竟线程数乘以栈大小就是不小的开销。有人在 Windows 上遇到栈溢出第一反应是去系统里找“扩大栈空间”的办法。如果问题是递归太深单纯把栈调大只是把崩溃时间往后移根本解决办法是改成迭代或限制递归深度。一句话区分堆溢出是“对象太多空间放不下”栈溢出是“调用太深调用帧被顶穿”。排查方向完全不同千万别一看到 StackOverflow 就去调 JVM 堆参数那一顿操作对栈问题完全无效。5. 实战避坑堆存储使用中的高频问题5.1 数据结构堆实现里的几个致命细节先列几个我自己踩过、也看过别人踩的坑下滤时数组越界只判断左孩子是否越界忽略右孩子边界导致访问到已释放或空位置。标准做法是在 left size 的前提下把 right 的比较限制为 right size或者把 left 不存在当作循环终止条件。比较器方向写反Java 的 PriorityQueue 默认是最小堆要实现最大堆需要传入反序比较器。刷题时在“前 K 个最大”和“前 K 个最小”之间来回套最后取出的集合经常反了。扩容带来的内存开销动态数组扩容通常是两倍扩容堆在插大量元素时会频繁复制。如果事先能大致估算数据规模直接预分配容量省掉中间多次 resize。这类问题在报错时往往不显眼表现通常是排序结果偶尔错、越界偶发崩溃非常难查。我的经验是写完堆结构先用一批随机数据做一次“先全部插入再依次弹出堆顶”的单调性验证。如果输出不是严格有序说明实现里有方向性或边界问题这种验证能立刻暴露大部分错误。5.2 TopK 与“在一堆数据里凑出一个数”很多算法题表面是“在一堆数据里找目标”本质都能用堆做剪枝或加速。最典型的是 TopK从海量数据里找最大的 K 个数用一个小根堆维护当前最大的 K 个数。堆顶是这 K 个里的最小值新数据比堆顶大就把堆顶替换掉再做一次下滤。整个过程扫描一遍数据时间复杂度 O(N log K)内存只需要 K 个元素的空间比全排序的 O(N log N) 省很多。“在一堆数据里凑出一个数”这种描述如果数据是静态的可以配合双指针或前缀和如果数据会动态插入删除又要求随时拿到当前最大值、最小值、中位数那堆基本就是标准答案。竞赛里常出现的题比如“在墙角堆放着一堆完全相同的正方体小木块”如果限制内存只有 16MB、时间 1000ms基于数组的堆就特别占优势不需要存指针不需要维护节点对象所有数据在连续数组里内存开销比平衡树小一半以上。这也是为什么很多竞赛选手明明会用 TreeMap还是坚持手写堆。5.3 内存参数调整的正确姿势JVM 内存参数不是越大越好。我把常见报错整理成对应关系方便排查时对照现象常见原因优先处理方向Java heap space对象堆积过多、GC 后仍无法分配排查泄漏、确认大对象再调 XmxGC overhead limit exceededGC 频繁且回收率极低排查引用链、考虑调整老年代占比Metaspace 报错加载类过多或动态生成类调 -XX:MaxMetaspaceSize重点排查动态类StackOverflowError递归过深或调用栈过大优先改迭代必要时才调 Xss系统内存持续上涨堆正常但堆外内存增长用 NMT 定位 Direct Memory、Native 区域调试建议分两层看。第一层看堆内用 jstat -gc 观察 GC 次数和堆占用趋势第二层看整个进程用 jcmd 看 Native Memory Tracking。堆内堆外都正常但系统还是飘再往操作系统一级排查比如文件句柄、线程数、共享内存。把每个层面的数据量化出来而不是凭感觉猜是解决内存类问题最基本的态度。6. 参考实现一份可以直接抄作业的代码6.1 Java 版最小堆实现以 0 下标为例这是我在面试里常用的 Java 版最小堆骨架class MinHeap { private int[] heap; private int size; public MinHeap(int capacity) { heap new int[capacity]; size 0; } private int left(int i) { return 2 * i 1; } private int right(int i) { return 2 * i 2; } private int parent(int i) { return (i - 1) / 2; } public void push(int val) { if (size heap.length) grow(); heap[size] val; int i size; while (i 0 heap[i] heap[parent(i)]) { swap(i, parent(i)); i parent(i); } } public int pop() { int top heap[0]; heap[0] heap[--size]; int i 0; while (true) { int smallest i; if (left(i) size heap[left(i)] heap[smallest]) smallest left(i); if (right(i) size heap[right(i)] heap[smallest]) smallest right(i); if (smallest i) break; swap(i, smallest); i smallest; } return top; } private void grow() { heap Arrays.copyOf(heap, heap.length * 2); } private void swap(int i, int j) { int t heap[i]; heap[i] heap[j]; heap[j] t; } }关键点全在 pop 的下滤逻辑先假设当前节点最小再分别和左右孩子比较。孩子下标必须小于 size 才参与比较最后若无交换就退出循环。最容易被忽略的边界是右孩子下标等于 size此时右孩子不存在访问它会越界。6.2 Python 版堆操作Python 自带 heapq默认是最小堆工程里通常不需要手写。面试要求手写时思路和 Java 版本保持一致即可。真正常见的是把任意列表原地堆化或者用它实现前 K 个最大import heapq data [4, 10, 3, 5, 1] heapq.heapify(data) # 原地堆化O(n) heapq.heappush(data, 2) # 插入 top data[0] # 查看堆顶 min_val heapq.heappop(data) # 弹出堆顶 # 前 K 个最大用小根堆维护 def top_k(nums, k): heap nums[:k] heapq.heapify(heap) for x in nums[k:]: if x heap[0]: heapq.heapreplace(heap, x) return heap这段 top_k 有个值得说明的细节heapreplace 等价于先 pop 再 push但只需要一次下滤比分开调两个方法要快。前 K 个最大对应小根堆前 K 个最小对应大根堆方向千万别记反。如果数据量极端到内存放不下全部这个写法照样有效因为堆里始终只保留 K 个元素。6.3 面试考察点与延伸手写堆这个题目面试官想确认的事情一般有三类一是完全二叉树性质是否真正理解二是下标转换能否无参考地推导出来三是上滤和下滤的循环终止条件是否严格。再往深问就是堆排序、合并 K 个有序链表、数据流中位数。这些题目本质上都是围绕“堆的数组存储”做的变化。数据流中位数的做法是维护一个大根堆和一个小根堆让两堆元素数量差不超过 1中位数就在两个堆顶附近合并 K 个有序链表则是每次都从 K 个链头中取最小取出后补上该链表的下一个节点小根堆正好胜任。这些场景里的堆仍然是数组存储真正变化的只是你想让堆“排出”什么样的序。还有一些高级扩展比如索引堆支持在 O(log n) 时间内修改任意位置的值因为它额外维护了节点位置与数组下标之间的反向映射再比如斐波那契堆能把插入摊还到 O(1)但常数大、实现复杂工程上还是二叉堆更常用。理解数组存储是地基后面所有变种都是在这层地基上加索引、加指针。我自己的体会是学堆的时候别只盯着代码看拿一张纸把“数组下标转树节点”这个过程多画几遍画到条件反射的程度再把大根堆和小根堆各实现一遍插入、删除、堆化全部手写。写错了也没关系关键是知道错在哪一步。数据结构里很多问题并不高深卡住你的往往就是对底层存储形式缺乏直觉。把数组和树之间的那一步想明白堆的问题就解决了一大半。