数组实现最大堆与提取最大值实战

作者:技术拾光

时间:2026-05-14

浏览:612

数组实现的最大堆通过索引映射模拟完全二叉树,维持父节点大于等于子节点的秩序。其核心价值在于动态高效维护数据集,支持快速获取最大值。插入时追加元素并上浮调整,删除最大值时取堆顶、补末尾并下沉重组。该结构在实时排行榜、优先队列等场景中优势显著,能以常数时间获取

文章目录

数组实现最大堆:动态维护数据流中的峰值

用数组实现最大堆,本质是在一维数组中模拟一棵完全二叉树,并通过一套索引计算规则,维持“父节点值永远大于等于子节点值”的核心秩序。这种结构的设计目的,并非为了在静态数据中寻找一次最大值——那种情况使用 max() 函数即可。它的真正优势在于能动态、高效地维护一个持续变化的数据集,让你能以极快的速度反复获取当前的最大值。无论是实时更新的排行榜、优先任务队列,还是流式数据中的峰值监控,数组堆都是背后的经典引擎。

数组实现最大堆与提取最大值实战

数组下标与父子节点的对应关系

所有操作都建立在索引映射这一基础之上。假设数组索引从0开始(这是PHP等多数语言的默认方式),那么对于数组中任意位置 i 的元素,其家庭成员的位置可以通过固定公式快速定位:

  • 父节点索引 = (int)(($i - 1) / 2)
  • 左子节点索引 = $i * 2 + 1
  • 右子节点索引 = $i * 2 + 2

举例说明:索引0是根节点,它的左孩子是1,右孩子是2。索引3的父节点是 (3-1)/2 = 1;索引4的父节点同样是 (4-1)/2 = 1(整除结果)。这套关系是后续所有“上浮”和“下沉”调整操作的基础。

插入新元素:先追加,再上浮调整

当有新元素需要加入堆时,策略是直接的:先将其追加到数组末尾,再根据情况将其“上浮”到合适的位置。因为新元素可能比它的父节点值大,这会破坏堆序性,需要通过“上浮”操作来修复。

  • 第一步,执行 array_push($heap, $value),将新值放到堆尾。
  • 第二步,记录它的位置:$i = count($heap) - 1。
  • 第三步,开始循环“上浮”:只要满足 $heap[$i] > $heap[(int)(($i-1)/2)](即比父节点大),就与父节点交换位置,并将当前位置 $i 更新为父节点的索引。
  • 循环持续直到该元素到达根节点(索引0),或者不再大于其父节点时停止。

来看一个实例:向最大堆 [50, 30, 40, 10, 20, 35] 中插入15。追加后数组变为 [50, 30, 40, 10, 20, 35, 15]。新元素15位于索引6,其父节点是索引2(值为40)。由于15小于40,不满足交换条件,插入过程完成,堆序性依然保持。

提取并删除最大值:取堆顶、补末尾、再下沉

最大值始终位于堆顶(索引0)。删除它时有一个技巧:不能简单地将它从数组中移除,那样会破坏完全二叉树的结构。正确的做法是进行替换。

  • 首先,取出最大值:$max = $heap[0]。
  • 接着,将数组的最后一个元素移到堆顶:$heap[0] = array_pop($heap)。
  • 最后,关键的一步:这个被放到顶端的“末尾元素”很可能不符合堆序,需要执行“下沉”操作(siftDown(0)),让它找到自己正确的位置。

下沉的逻辑是:比较当前节点与其左右子节点中较大的那一个。如果当前节点比那个子节点小,就交换它们的位置,然后继续从新的子节点位置向下比较。这个过程一直持续到当前节点大于等于它的所有子节点,或者已经下沉到叶子节点为止。

实现时需注意边界:左子索引 $left = $i * 2 + 1 必须小于当前堆的大小,右子索引同理。如果只有左子节点,那就只和左子节点比较。

实战应用:动态获取数据流中的最大值

设想一个实际场景:你正在监控一系列实时传入的温度读数,需要随时知道当前最高的温度值,并且这个数据集会不断新增,偶尔还需要移除无效的峰值。

  • 初始化:$tempHeap = []; 创建一个空堆。
  • 持续插入:insert($tempHeap, 28); insert($tempHeap, 32); insert($tempHeap, 29); … 每个新读数都通过插入操作入堆。
  • 瞬时取最大值:任何时候,当前最高温就是 $tempHeap[0] null;。这是O(1)时间复杂度,无需遍历整个数组。
  • 移除最大值后:如果某个最高值被判定为无效需要剔除,调用 $removed = deleteMax($tempHeap);。堆会自动内部重组,之后 $tempHeap[0] 给出的就是新的最大值。

与每次调用 max($array) 都需要全量扫描O(n)相比,堆结构在频繁增删的场景下优势巨大。它将“获取最大值”的成本锁定在常数时间,而“删除并重组”的成本也仅是对数级别,堪称管理动态极值问题的利器。

实用工具推荐

电子包浆

绿化、压缩、噪点和虚拟水印,自由调节做旧程度。

使用 ›
图片压缩

选择画质和输出格式,预览压缩前后的大小。

使用 ›