第 6 章 优先队列

Priority Queue and Heap

为什么需要优先队列

普通队列按照到达顺序服务。

优先队列按照优先级服务。

典型场景：

  • 操作系统任务调度
  • Dijkstra 最短路
  • Huffman 编码
  • 事件模拟
  • Top-K 查询
  • 堆排序

Linux 调度器要在就绪任务中选择下一项

Kafka 延迟、重试和时间驱动事件处理

PostgreSQL Top-N、排序和查询执行计划

C++ STL std::priority_queue 封装堆操作

学习目标

  • 掌握优先队列 ADT
  • 比较无序线性表、有序线性表和堆实现
  • 掌握最大堆、最小堆和完全二叉树数组表示
  • 掌握插入的上滤和删除堆顶的下滤
  • 掌握 Floyd 建堆和复杂度分析
  • 理解堆排序为什么不稳定
  • 使用堆解决第 K 大元素问题

路线图

G adt 优先队列 ADT linear 线性表实现 adt->linear heap 二叉堆定义 linear->heap array 数组下标映射 heap->array ops 上滤 / 下滤 array->ops build Floyd 建堆 ops->build apps 堆排序 / Top-K build->apps

Priority Queue ADT

最大优先队列：

操作 含义
create() 创建空优先队列
size() 返回元素个数
max() 返回最大优先级元素
insert(x) 插入元素
deleteMax() 删除并返回最大优先级元素

最小优先队列把 max/deleteMax 换成 min/deleteMin。

线性表实现

表示 插入 查找最大 删除最大
无序线性表 \(\Theta(1)\) \(\Theta(n)\) \(\Theta(n)\)
有序线性表 \(\Theta(n)\) \(\Theta(1)\) \(\Theta(1)\) 或 \(\Theta(n)\)
二叉堆 \(O(\log n)\) \(O(1)\) \(O(\log n)\)

堆在插入和删除之间取得平衡。

堆定义

最大堆满足：

  • 是完全二叉树
  • 每个结点的值不小于它的孩子

最小堆满足：

  • 是完全二叉树
  • 每个结点的值不大于它的孩子

堆不要求左右子树之间有全局有序关系。

最大堆示例

G 87 87 78 78 87->78 53 53 87->53 45 45 78->45 65 65 78->65 9 9 53->9 31 31 53->31 17 17 45->17 23 23 45->23

根结点一定是最大值。

数组表示

堆是完全二叉树，适合用数组紧凑存放。

若使用 1-based 下标：

\[ parent(i)=\lfloor i/2\rfloor \]

\[ left(i)=2i,\quad right(i)=2i+1 \]

空出 heap[0] 可以让公式更简单。

上滤与下滤

最大堆类骨架

template <class T>
class MaxHeap {
 public:
  explicit MaxHeap(int capacity = 16);

  int size() const { return currentSize_; }
  bool empty() const { return currentSize_ == 0; }
  const T& max() const;
  void insert(const T& value);
  T deleteMax();
  void initialize(std::vector<T> values);

 private:
  std::vector<T> heap_;  // 1-based
  int currentSize_ = 0;
};

插入：上滤代码

template <class T>
void MaxHeap<T>::insert(const T& x) {
  if (currentSize_ + 1 == static_cast<int>(heap_.size())) {
    heap_.resize(heap_.size() * 2);
  }
  int hole = ++currentSize_;
  while (hole > 1 && x > heap_[hole / 2]) {
    heap_[hole] = heap_[hole / 2];
    hole /= 2;
  }
  heap_[hole] = x;
}

新元素沿父指针向上移动，最多经过树高层。

删除堆顶：下滤代码

template <class T>
T MaxHeap<T>::deleteMax() {
  if (empty()) throw std::underflow_error("empty heap");
  T answer = heap_[1];
  T last = heap_[currentSize_--];
  int hole = 1;
  while (hole * 2 <= currentSize_) {
    int child = hole * 2;
    if (child != currentSize_ && heap_[child] < heap_[child + 1]) {
      ++child;
    }
    if (last >= heap_[child]) break;
    heap_[hole] = heap_[child];
    hole = child;
  }
  heap_[hole] = last;
  return answer;
}

下滤时总是选择更大的孩子。

单次操作复杂度

堆高为：

\[ \lfloor \log_2 n \rfloor \]

因此：

操作 时间
max() \(O(1)\)
insert() \(O(\log n)\)
deleteMax() \(O(\log n)\)

建堆方法一：逐个插入

逐个插入 \(n\) 个元素。

每次插入最坏 \(O(\log n)\)。

总时间：

\[ O(n\log n) \]

这种方法简单，但不是最优建堆。

建堆方法二：Floyd 建堆

Floyd 建堆代码

把所有元素先放入数组，再从最后一个内部结点开始下滤：

template <class T>
void MaxHeap<T>::initialize(std::vector<T> values) {
  currentSize_ = static_cast<int>(values.size());
  heap_.assign(currentSize_ + 1, T{});
  for (int i = 0; i < currentSize_; ++i) {
    heap_[i + 1] = values[i];
  }
  for (int i = currentSize_ / 2; i >= 1; --i) {
    percolateDown(i);
  }
}

Floyd 建堆复杂度

靠近叶子的结点很多，但下滤距离短。

靠近根的结点少，虽然下滤距离长。

总工作量为：

\[ \sum_{h\ge 0} \frac{n}{2^{h+1}}h = O(n) \]

因此 Floyd 建堆是线性时间。

堆排序

堆排序流程

堆排序流程：

  1. 将 \(n\) 个元素建成最大堆
  2. 反复删除最大元素
  3. 最大元素从后向前放入数组

复杂度：

\[ O(n)+nO(\log n)=O(n\log n) \]

堆排序原地，但不稳定。

为什么堆排序不稳定

稳定排序要求相等关键字保持原相对顺序。

堆排序中，元素会沿树路径与远处元素交换。

相同关键字可能跨越彼此，因此堆排序通常不稳定。

第 K 大元素

第 K 大元素算法

方法一：建最大堆。

  • 建堆 \(O(n)\)
  • 执行 \(k\) 次 deleteMax
  • 总时间 \(O(n+k\log n)\)

方法二：维护大小为 \(k\) 的最小堆。

  • 前 \(k\) 个元素建最小堆 \(O(k)\)
  • 之后每个元素若大于堆顶，则替换堆顶并下滤
  • 总时间 \(O(n\log k)\)

当 \(k\ll n\) 时，方法二更合适。

Top-K 代码

int kthLargest(const std::vector<int>& a, int k) {
  std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
  for (int x : a) {
    if (static_cast<int>(pq.size()) < k) {
      pq.push(x);
    } else if (x > pq.top()) {
      pq.pop();
      pq.push(x);
    }
  }
  return pq.top();
}

堆顶始终是当前前 \(k\) 大元素中的最小者。

应用：事件模拟

离散事件模拟维护一组未来事件。每次取出时间最早的事件执行，执行过程中又可能产生新的未来事件。

用最小优先队列保存事件，可以把“取下一事件”和“插入新事件”都控制在 \(O(\log n)\)。

多维分析

维度 二叉堆
结构 完全二叉树
存储 数组，无指针
查找堆顶 \(O(1)\)
插入 上滤，\(O(\log n)\)
删除堆顶 下滤，\(O(\log n)\)
建堆 Floyd，\(O(n)\)
随机查找 不支持高效查找任意 key
稳定性 堆排序不稳定

练习 1：最小堆插入 3

已知序列：

\[ 5,8,12,19,28,20,15,22 \]

是最小堆，插入 \(3\)。

过程：

  • 3 放到末尾
  • 与父结点 19 比较，3 上滤
  • 与父结点 8 比较，3 上滤
  • 与父结点 5 比较，3 上滤到根

结果根为 3。

练习 2：判断是否为堆

判断数组是否为最大堆：

bool isMaxHeap(const std::vector<int>& heap) {
  int n = static_cast<int>(heap.size()) - 1;
  for (int i = 1; i * 2 <= n; ++i) {
    int left = i * 2;
    int right = left + 1;
    if (heap[i] < heap[left]) return false;
    if (right <= n && heap[i] < heap[right]) return false;
  }
  return true;
}

只需要检查所有内部结点。

练习 3：堆排序复杂度

堆排序建堆是 \(O(n)\)。

之后执行 \(n-1\) 次删除堆顶，每次 \(O(\log n)\)。

总复杂度：

\[ O(n\log n) \]

额外空间可以做到 \(O(1)\)，但排序不稳定。