通过动态可视化,让你彻底理解两者的关系
数据结构——一种完全二叉树,每个节点的值都不大于(或不小于)其父节点的值。
• 最大堆:父节点 ≥ 子节点 → 根是最大值
• 最小堆:父节点 ≤ 子节点 → 根是最小值
抽象数据类型——一种行为规范,规定"每次取出的元素是优先级最高的"。
• 只定义做什么(出队优先级最高的)
• 不规定怎么做(可以用堆、数组、链表实现)
堆是实现优先队列的一种方式(最常见、最高效的方式)。
打个比方:
• 优先队列 = "我想吃水果"(需求/接口)
• 堆 = "我买了苹果"(具体实现)
• 数组 = "我买了香蕉、草莓、葡萄"(其他实现方式)
| 实现方式 | 入队 | 出队 |
|---|---|---|
| 堆 | O(log n) | O(log n) |
| 有序数组 | O(n) | O(1) |
| 无序数组 | O(1) | O(n) |
堆是一种数据结构,优先队列是一种行为规范(ADT)。
堆是实现优先队列最高效的方式,但不是唯一方式。
就像:
• 队列 = "先进先出" ← 行为规范
• 数组/链表 = 具体实现
• 优先队列 = "优先级高的先出" ← 行为规范
• 堆 = 高效的具体实现