【算法与数据结构】二叉堆和优先队列 Priority Queue
2024-09-05 18:47:23
优先队列的特点
普通队列遵守先进先出(FIFO)的规则,而优先队列虽然也叫队列,规则有所不同:
- 最大优先队列:优先级最高的元素先出队
- 最小优先队列:优先级最低的元素先出队
优先队列可以用下面几种数据结构来实现:
- 基于堆 heap,包括下面几种堆:
- 二叉堆
- 多项式堆
- Fibonacci 堆
- 基于二叉搜索树 BST
如果用线性数据结构来实现优先级队列,则时间复杂度均为 O(n)。而如果用二叉堆来实现,时间复杂度可以提高到 O(logn)。下面以二叉堆为例。
实现二叉堆
二叉堆有两个限制:
- 二叉堆必须是完全二叉树(元素从上而下,自左至右排列)
- 二叉堆中任一父结点的值大于其左右两子节点的值(大顶堆,可以实现最大优先队列),或小于其左右两子节点的值(小顶堆,可以实现最小优先队列)
根据二叉堆上面的性质,可以用一个数组来保存二叉堆中的结点。其中,对于数组中任一个秩为 x 的元素,其对应二叉树中,父子结点的秩分别为:
- 父结点:r = (x - 1) /2
- 左子结点:r = 2x +1
- 右子结点:r = 2x + 2
二叉堆的构建,可以参考 这里。
最新文章
- AFNetworking 3.0 源码解读 总结(干货)(上)
- iOS学习-创建带下划线的button
- Javascript 事件对象(五)事件捕获
- [转]大型 JavaScript 应用架构中的模式
- OpenJudge计算概论-字符串最大跨距
- python 统计文本文件的行数
- 一个PHP书单 -摘自网络
- JAVA中IO技术:BIO、NIO、AIO
- STM32F4中USB与PC双向通信
- Coursera课程 Programming Languages, Part B 总结
- 聚沙成塔-linux 常用命令
- asp.net core 学习资料整理
- [Swift]LeetCode1022. 从根到叶的二进制数之和 | Sum of Root To Leaf Binary Numbers
- Notes for ";Python in a Nutshell";
- linux 配置ftp服务
- Java并发编程:线程池的使用(转载)
- CSS3之多列布局columns详解
- Java 基础 面向对象修饰符和自定义数据类型
- 开源截图工具cutycapt的安装及使用
- PL/SQL将sql脚本数据导入Oracle