堆的基本概念与结构
- 堆的定义：完全二叉树，满足堆性质（最大堆或最小堆）
- 存储方式：数组实现，父子节点索引关系
- 关键操作：上浮（Heapify Up）和下沉（Heapify Down）
优先队列的抽象数据类型
- 优先队列的核心操作：插入（Enqueue）、删除最高优先级元素（Dequeue）、查看队首元素（Peek）
- 与普通队列的区别：元素按优先级动态排序，而非先进先出
基于堆的优先队列实现原理
- 插入操作（Enqueue）流程
将新元素放入堆末尾，通过上浮操作调整堆结构 - 删除操作（Dequeue）流程
交换堆顶与末尾元素，删除末尾元素，通过下沉操作调整堆结构 - 查看队首元素（Peek）
直接返回堆顶元素（数组首元素）
时间复杂度分析
- 插入操作：O(log n)，上浮操作的树高度决定
- 删除操作：O(log n)，下沉操作的树高度决定
- 建堆操作：O(n)，Floyd建堆算法分析
- 查看队首元素：O(1)，直接访问数组首地址
空间复杂度与优化
- 空间复杂度：O(n)，数组存储所有元素
- 动态扩容策略：类似动态数组的倍数扩容机制
与其他实现的对比
- 无序数组：插入O(1)，删除O(n)
- 有序数组：插入O(n)，删除O(1)
- 对比结论：堆在动态场景下综合效率最优
实际应用场景
- 任务调度：操作系统进程优先级管理
- 图算法：Dijkstra最短路径中的优先级选择
- 数据流处理：实时获取Top K元素
