Summary

A priority_queue stores elements with a priority_key and always returns the item with highest priority. Key operations are top, push, pop, empty, and size. Time costs: top is O(1); push and pop are O(log n). Order is by priority, not arrival time. Common implementations include a binary_heap for typical use, or simple sorted_array and unsorted_array. Typical uses: task scheduling, Dijkstra shortest path, and A* search. In a min-priority queue, smaller keys mean higher priority.