跳到主要内容

优先队列

优先队列与普通队列有什么区别？​

  • 普通队列: 出队顺序由入队顺序决定, 先入先出;
  • 优先队列: 队列元素带有优先级, 优先级高的元素优先出列;
  • 本质: 出队顺序由优先级决定, 而不是由到达时间决定;

优先队列有哪些使用场景？​

  • 任务调度器: 高优先级任务先执行;
  • 查找第 k 个最小元素;
  • 需要反复取出当前极值的场景;

优先队列有哪几种实现方式？​

  • 数组或链表: 入队 O(1), 但取极值需要 O(n) 扫描;
  • 二叉堆: 可以用数组、链表或二叉堆实现, 常用二叉堆;
  • 二叉堆的代价: 入堆与出堆 O(log n), 访问堆顶 O(1);

优先级字段如何参与堆的比较？​

  • 做法: 堆中存放带优先级的数据, 例如 [值, 优先级] 二元组;
  • 改动: 下沉与上浮中的比较从元素本身换成优先级字段;
// 堆的骨架见 [堆与完全二叉树](./040-堆与完全二叉树.md)
// 唯一改动: 比较时取下标 1 的优先级字段
if (left < n && nums[left][1] > nums[max][1]) max = left;
if (right < n && nums[right][1] > nums[max][1]) max = right;