优先队列(堆实现)
2021-09-18 16:55:18 3 举报AI智能生成
优先队列(堆实现)
作者其他创作
大纲/内容
优先队列的概念
优先队列中的<font color="#ff0000">每个元素都有各自的优先级</font>
<font color="#ff0000">优先级最高的元素 最先</font><font color="#000000">得到服务</font>
<font color="#ff0000">优先级相同的元素</font>按照其在<font color="#ff0000">优先队列中的顺序</font>得到服务
优先队列至少需要支持下述操作
a.插入带优先级的元素
b.取出具有最高优先级的元素
c.查看最高优先级的元素。
优先队列的实现<br>
实现优先队列的候选数据结构包括：有序序列、无序序列、堆。
有序序列
有序序列中存储的数据都是有序的，在执行insert操作复杂度为O(N)
执行N次时，最大复杂度为O(N^2)
无序序列
无序序列中存储的元素是无序的，在执行insert操作复杂度为O(1)
执行N次时，最大复杂度为O(N^2)
堆结构<br>
堆中insert和get的复杂度都为O(logN)
执行N次时，最大复杂度为O(NlogN)
代码实现
基本属性定义
储存数组 - arr<br>允许储存元素最大值 - limit<br>当前元素个数 - len<br>
初始化<br>
1. 初始化元素数组 arr<br>2. 提取最大堆元素到堆顶 - maxheap()<br>
基本功能<br>
插入insert
1. 将元素插入堆尾<br>2. 提取最大堆元素到堆顶 - maxheap()<br>
弹出pop
1. 弹出堆顶元素<br>2. 将堆尾元素提到堆顶<br>3. 提取最大堆元素到堆顶 - maxheap()
查询get
1. 返回堆顶元素
提取最大堆元素到堆顶maxheap
堆中，下标为index的元素<br>它的父节点为（index-1）/ 2<br>它的左子节点为 2*index + 1， 右子节点为 2*index + 2<br>
先比较左右节点， 获得最大节点
最大节点 和 父节点比较，交换
递归处理每个堆，这时堆顶就是最大值
优先队列的应用
TopN问题
问题：获取数组的第K大元素<br>思路：从无序堆中遍历，弹出堆顶元素K次
贪心算法又称贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。
0 条评论
下一页
