A priority queue is an abstract data type, meaning it is defined by what it does rather than how it is built. It holds a collection of elements, each with a priority, and supports two main operations: insert a new element, and remove and return the element of highest priority. Unlike an ordinary queue, which serves items in the order they arrived, a priority queue ignores arrival order entirely and always hands back the most important item next. The priority might be the smallest distance, the earliest deadline, or the soonest scheduled event.
The standard implementation is a heap, a tree-shaped structure in which every parent’s priority is at least as high as its children’s. The MIT 6.006 lecture on binary heaps shows how a heap supports both insertion and extraction of the top element in time proportional to the logarithm of the number of items, by storing the tree compactly in an array and restoring the heap property with a short chain of swaps after each change. A naive implementation using an unsorted list could insert quickly but would need a full scan to find the highest-priority item; a sorted list would find it instantly but pay a high cost on every insertion. The heap balances both at logarithmic cost.
Priority queues turn up wherever the next thing to handle is the most urgent rather than the oldest. Operating systems use them to schedule processes by priority. Discrete-event simulations use them to always process the next event in time order. The MIT 6.006 lecture on Dijkstra’s algorithm relies on a priority queue at the core of shortest-path computation: it repeatedly extracts the unvisited node with the smallest known distance, which is what lets the algorithm settle nodes in order of increasing distance from the source.
Because the priority queue is an interface, not a fixed structure, the same algorithm can be sped up by swapping in a faster underlying implementation. Plain binary heaps give logarithmic operations; more elaborate heaps reduce the cost of certain updates further. This separation between the abstract operations and the concrete data structure is exactly what makes the priority queue such a reusable building block across scheduling, simulation, and graph algorithms.