首页 > 代码库 > 算法笔记2-优先队列(堆)(上)
算法笔记2-优先队列(堆)(上)
一、什么是优先队列?
看一情景:我们去KTV唱歌,点歌的时候,可以发现所点的歌就是一个队列。
这时候,一个MM突然不玩手机了想唱歌,于是她来点歌,并且想尽早轮到她。
于是她可以选择“插歌”这个功能插到前排队列里。
这种具备可以插入优先权元素的队列,就叫优先队列。但是,这个定义不是严谨的。
优先队列的基本模型是这样的——
具备两个功能:
- insert插入;
- deleteMin删除最小者。
它的工作就是——
它很有用哦,具体可以用在操作系统,外部排序和贪婪算法中等。
二、怎么实现优先队列?
1、用链表
- 方案A:链表乱序,以O(1)的代价插入,以O(N)的代价遍历该链表来删除最小元素。
- 方案B:让链表始终保持排序状态,然后删除得代价就是O(1),但是插入的代价就相对高了,是O(N);
比较——
一般而言,删除最小的操作从来很少会有多余插入操作的时候,因此方案A要比B要好些。
2、用二叉查找树
二叉查找树对于两种操作的运行时间都是O(logN)。不过可能有点过分了,因为二叉查找树可以做的功能远多于此,有点杀鸡用牛刀的嫌疑。因此,我们将使用比较合适的数据结构——二叉堆。
三、二叉堆
1、什么是二叉堆?
满足如下结构性和堆序性,即为二叉堆。
结构性质:堆是一棵被完全填满的二叉树,有可能的例外是在底层,底层上的元素从左到右填入。这样的树称为完全二叉树。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。