Priority queue

Applies to: cpp, general

A priority queue always removes the highest-priority element first, regardless of insertion order. It is usually a binary heap, giving O(log n) insert and extract. It powers Dijkstra and A* path planning. C++'s std::priority_queue is a max-heap by default.

std::priority_queue<int> pq;          // max-heap
pq.push(3); pq.push(1); pq.push(5);
pq.top();                             // 5

See also: queue, big-o