树与层次结构

优先队列

优先队列是一种抽象数据类型——它描述的是行为，而不是某种具体的存储布局。普通队列按先进先出的顺序处理元素；优先队列则总是优先处理优先级最高的那个元素，无论它何时到达。想想急诊室：最危急的病人先被诊治，而不是最早走进门的那位。

它的接口很小：按优先级压入一个元素，再弹出（或查看）当前最紧急的那个。由于这正是堆所擅长的形状，优先队列几乎总是用二叉堆实现，于是压入和弹出都是 O(log n)，查看是 O(1)。它也可以用别的结构支撑——有序数组、平衡树——但堆是标准选择，因为它快且不需要指针。

把这个抽象数据类型与支撑它的堆分开，正是要点所在：你只针对“把当前最紧急的元素给我”来编程，让库去挑选底层结构。在 C++ 中就是 std::priority_queue，默认是大顶堆。优先队列是 Dijkstra 最短路、Prim 最小生成树、事件驱动仿真和 Huffman 编码背后的引擎——凡是你需要反复取出当前最优或最小者的地方都用得上。

std::priority_queue<int> pq;   // max-heap by default
pq.push(3);
pq.push(9);
pq.push(5);
while (!pq.empty()) {
  std::cout << pq.top() << ' ';  // prints 9 5 3
  pq.pop();
}

std::priority_queue——披着队列接口的大顶堆。

C++ 的 std::priority_queue 默认是大顶堆；传入 std::greater（或对键取反）即可得到最小优先队列。

又称

PQ优先级队列优先权队列優先權佇列

另见

堆队列抽象数据类型最短路径

← 全部术语