索引优先队列是什么？它为什么能支持修改优先级？

简化版

索引优先队列可以理解成「堆 + 下标映射表」。

普通优先队列只擅长取出堆顶，但如果要修改某个指定元素的优先级，往往不知道它在堆数组的哪个位置，只能线性查找。索引优先队列会额外维护 key -> heapIndex 的映射，定位到元素后再根据优先级变化执行上浮或下沉。

所以它适合 Dijkstra、任务调度、排行榜更新这类「元素优先级会变化」的场景。

详细版

普通堆通常只维护一个数组，例如小顶堆中 heap[0] 是最小元素。插入、弹出堆顶都可以做到 O(log n)，但如果想把某个元素的优先级从 10 改成 3，问题就来了：这个元素可能在数组任意位置。

索引优先队列的核心是维护两层信息：

结构	作用
堆数组	保证堆序，快速取出最高优先级元素
位置表	记录某个 key 当前在堆数组中的位置
优先级表	保存 key 对应的 priority

当修改优先级时，先通过位置表定位数组下标，再比较新旧优先级。如果新优先级更高，执行上浮；如果更低，执行下沉。

decreaseKey(key, newPriority):
  i = pos[key]
  priority[key] = newPriority
  siftUp(i)

这样修改优先级的复杂度可以从 O(n + log n) 降到 O(log n)。

完整版教学

1. 先抓住普通优先队列的短板

普通优先队列解决的是「每次拿当前最重要的元素」。

它的强项很明确：

插入一个元素：O(log n)
查看堆顶：O(1)
删除堆顶：O(log n)

但它有一个面试里经常被追问的短板：如果要删除或更新一个非堆顶元素，普通堆并不知道这个元素在哪里。

比如堆数组是：

index: 0  1  2  3  4
value: 2  5  4  9  7

如果你要把任务 taskA 的优先级从 9 改成 1，普通优先队列需要先扫描数组找到 taskA，这一步就是 O(n)。

只要题目出现「更新某个指定元素的优先级」，就要警惕普通堆定位能力不足。

2. 索引优先队列多维护了什么

索引优先队列不是一种完全陌生的新结构，它仍然以堆为主体，只是额外维护映射。

常见设计如下：

名称	示例	含义
`heap`	`[A, C, B]`	堆数组，存 key
`pos`	`{A:0, C:1, B:2}`	key 在堆数组中的位置
`priority`	`{A:3, B:8, C:5}`	key 的优先级

堆比较时不直接比较 key，而是通过 priority[key] 判断谁更靠前。

3. 为什么交换元素时位置表也必须更新

索引优先队列最容易写错的地方，是只交换堆数组，不同步更新 pos。

例如：

swap(heap[i], heap[j])
pos[heap[i]] = i
pos[heap[j]] = j

如果忘了更新 pos，后续 decreaseKey(A) 可能拿到旧位置，轻则堆序错乱，重则修改到另一个元素。

这一点在面试里很好讲：索引优先队列的正确性来自「堆数组和位置表始终互为反向索引」。

4. 修改优先级后为什么有时上浮、有时下沉

以小顶堆为例：

优先级变小，元素应该更靠近堆顶，所以执行上浮。
优先级变大，元素可能应该下移，所以执行下沉。
如果不确定新旧方向，也可以先上浮再下沉，仍然是 O(log n)。

伪代码可以这样写：

changePriority(key, newPriority):
  i = pos[key]
  old = priority[key]
  priority[key] = newPriority

  if newPriority < old:
    siftUp(i)
  else:
    siftDown(i)

5. 和懒删除方案有什么区别

普通优先队列也能用懒删除绕过「删除任意元素」的问题：更新时不改旧元素，而是插入一个新版本；弹出堆顶时检查版本是否过期。

二者区别如下：

方案	修改优先级	删除旧数据	空间占用	适合场景
索引优先队列	直接定位后上浮/下沉	立即维护	较稳定	需要频繁更新
懒删除	插入新版本	弹出时清理	可能膨胀	实现简单、更新量可控

面试回答时可以说：懒删除是工程上常见的简化方案，索引优先队列是更严格的数据结构方案。

6. 典型应用：Dijkstra 中的 decrease-key

Dijkstra 算法里，如果发现到某个节点的更短距离，就需要降低该节点的优先级。

有两种做法：

用普通优先队列，把新的 (distance, node) 再插入一次，旧记录懒删除。
用索引优先队列，直接对 node 执行 decreaseKey。

理论上，索引优先队列更贴近 decrease-key 操作；工程中，很多语言标准库没有索引堆，所以更常见的是懒删除写法。

7. 复杂度怎么回答

索引优先队列的复杂度可以这样记：

操作	复杂度	原因
`push`	`O(log n)`	插入后上浮
`peek`	`O(1)`	堆顶直接访问
`poll`	`O(log n)`	删除堆顶后下沉
`changePriority`	`O(log n)`	位置表定位 `O(1)`，调整堆 `O(log n)`
`contains`	`O(1)`	查位置表

这也是它相比普通堆最核心的价值：更新指定元素时不再需要 O(n) 扫描。

8. 常见误区与追问

误区：索引优先队列只是给堆元素加一个 id。 真正关键是维护 id -> heapIndex 的位置映射，否则仍然无法快速定位。
误区：修改优先级后只需要改 priority 表。 改完后堆序可能被破坏，必须上浮或下沉。
误区：交换堆数组元素不需要更新位置表。 位置表一旦过期，后续更新会定位错误。
追问：普通优先队列能不能实现类似效果？ 可以用懒删除，但空间可能增加，并且堆顶弹出时要过滤过期数据。
追问：索引优先队列适合所有场景吗？ 不一定，如果只插入和弹出堆顶，普通堆更简单；只有频繁修改指定元素时才更值得。

简化版

详细版