数据结构与算法

数据结构与算法知识详解
帅旋
关注
充电
IT宅站长,技术博主,共享单车手,全网id:arthinking。

索引式优先队列数据结构

发布于 2020-04-28 | 更新于 2024-03-11

8、索引式优先队列 IPQ

索引优先级队列(Indexed Priority Queue IPQ)是传统的优先级队列变体,除了常规的PQ操作之外,它还提供了索引用于支持键值对的快速更新和删除。

我们知道前面的优先级队列的元素都是存放到一个list里面的,我们想知道知道某一个值在优先级队列中的位置,也是需要遍历一个个对比才知道的,要是有重复的值,那就区分不了了。既然找不到元素,那么对元素的更新和删除也就无从说起了。

为此,我们引入了如下两个索引:节点索引ki位置索引im

image-20200425180414114

如:

  • 请查找节点ki所在的优先级位置:可以很快可以从表1中找到 pm[ki];
  • 请查找优先级位置im存的是什么节点:可以很快从表2中找到节点的索引 ki[im]

与构造或更新删除PQ不同的是,IPQ需要额外维护这些索引的关系。

8.1、时间复杂度

操作 时间复杂度
delete(ki) O(log(n))
valueOf(ki) O(1)
contains(ki) O(1)
peekMinKeyIndex() O(1)
pollMinKeyIndex() O(log(n))
peekMinValue() O(1)
pollMinValue() O(log(n))
insert(ki, value) O(log(n))
update(ki, value) O(log(n))
decreaseKey(ki, value) O(log(n))
increaseKey(ki, value) O(log(n))

8.2、编程实践

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/dsa/indexed-priority-queue.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。