8、索引式优先队列 IPQ
索引优先级队列(Indexed Priority Queue IPQ)是传统的优先级队列变体,除了常规的PQ操作之外,它还提供了索引用于支持键值对的快速更新和删除。
我们知道前面的优先级队列的元素都是存放到一个list里面的,我们想知道知道某一个值在优先级队列中的位置,也是需要遍历一个个对比才知道的,要是有重复的值,那就区分不了了。既然找不到元素,那么对元素的更新和删除也就无从说起了。
为此,我们引入了如下两个索引:节点索引ki
和位置索引im
:
如:
- 请查找节点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)) |