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