Priority queue
A queue where elements are ordered by priority, with highest priority elements dequeued first. Priority queues enable scheduling and optimization algorithms. Implementation varies: sorted list, heap, or binary search tree. Different priorities for equal elements create stable orderings.
Formula
Heap enqueue/dequeue = O(log n); Sorted list enqueue = O(n), dequeue = O(1)
Real World
Hospital A&E departments like the NHS triage system use priority queues — a patient with chest pain is seen before someone with a sprained ankle, regardless of arrival time.
Exam Focus
When asked to 'explain' a priority queue, always distinguish it from a standard queue by stating items are ordered by priority, not arrival.
How well did you know this?