🔄 优先队列 vs 堆 🔍

通过动态可视化,让你彻底理解两者的关系

🌲 堆 (Heap)

数据结构——一种完全二叉树,每个节点的值都不大于(或不小于)其父节点的值。

最大堆:父节点 ≥ 子节点 → 根是最大值
最小堆:父节点 ≤ 子节点 → 根是最小值

📋 优先队列 (Priority Queue)

抽象数据类型——一种行为规范,规定"每次取出的元素是优先级最高的"。

• 只定义做什么(出队优先级最高的)
• 不规定怎么做(可以用堆、数组、链表实现)

🔗 两者的关系

堆是实现优先队列的一种方式(最常见、最高效的方式)。

打个比方:
优先队列 = "我想吃水果"(需求/接口)
= "我买了苹果"(具体实现)
数组 = "我买了香蕉、草莓、葡萄"(其他实现方式)

📐 概念层次关系

优先队列
(抽象数据类型)
规定行为:
每次出队优先级最高的
堆实现 ✓
O(log n) 入/出
数组实现
O(n) 入 / O(1) 出
链表实现
O(n) 入 / O(1) 出
...
💡 堆是优先队列最常用的实现方式,但不是唯一方式!

🌲 最小堆结构(树视图)

📊 底层数组存储

📝 操作日志

点击按钮开始操作,观察堆的变化过程...

🔬 插入操作详解(插入 3)

堆的调整过程

点击下方按钮,分步观察插入过程

数组对应的变化

索引关系:
• 父节点索引 = (i - 1) / 2
• 左子节点 = 2i + 1
• 右子节点 = 2i + 2

🔬 弹出最小操作详解

堆的调整过程

点击下方按钮,分步观察弹出过程

复杂度对比

实现方式 入队 出队
O(log n) O(log n)
有序数组 O(n) O(1)
无序数组 O(1) O(n)
堆的插入和弹出都是 O(log n),综合效率最高,这就是为什么优先队列常用堆实现!

💡 一句话总结

堆是一种数据结构优先队列是一种行为规范(ADT)。
堆是实现优先队列最高效的方式,但不是唯一方式。

就像:
队列 = "先进先出" ← 行为规范
数组/链表 = 具体实现

优先队列 = "优先级高的先出" ← 行为规范
= 高效的具体实现