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)) |