Priority Queue

An ordinary queue removes elements in the order they arrived, first in, first out. A priority queue removes elements according to a different rule entirely: whichever element has the highest (or lowest) priority goes first, regardless of when it arrived.

Priority Queue

A hospital emergency room is the standard example: patients are not treated in arrival order, but by urgency.

Normal patient     priority 1
Urgent patient      priority 4
Critical patient    priority 5

A critical patient who just walked in is treated before a normal patient who has been waiting for an hour, since priority overrides arrival order.

Operations

Why a binary heap implements it

This mirrors a distinction already seen with stacks: a stack is an abstract behavior (LIFO), and an array or a linked list is one way to implement that behavior. Similarly:

Priority queue → the behavior (remove by priority)
Binary heap    → the data structure that implements it efficiently

Just as a stack could be implemented other ways (a plain array with O(n) push, for instance), a priority queue could too. The heap is the standard choice because its O(log n) insert and delete beat the worse bounds of a plain sorted or unsorted list.

A max-priority queue holding four patient priorities (P1=2, P2=5, P3=4, P4=1), stored as a max heap:

The highest priority, 5, sits at the root, index 0, exactly where peek looks, so no search across the other elements is needed.

Insert and delete, using the heap operations directly

Because a priority queue is a heap underneath, its insert and delete are literally the heap insertion (bubble-up) and heap root deletion (heapify-down) algorithms, just described in priority-queue terms:

PQ_INSERT(A, N, ITEM, PRIORITY)
// A is the array of (element, priority) pairs
// N is the current number of elements in the priority queue
// ITEM is the new element, PRIORITY is its priority
 
1. A[N] = (ITEM, PRIORITY)
2. i = N
3. N = N + 1
 
4. While i > 0:
       parent = (i - 1) / 2      (integer division)
 
       If A[parent].priority >= A[i].priority:
           Break
 
       Swap A[parent] and A[i]
       i = parent
 
5. Return

PQ_DELETE_MAX(A, N)
// A is the array of (element, priority) pairs
// N is the current number of elements in the priority queue
 
1. If N == 0:
       PRINT "UNDERFLOW"
       Return
2. MAX = A[0]
3. A[0] = A[N-1]
4. N = N - 1
5. HEAPIFY_DOWN(A, N, 0)   // same heapify-down used to delete a heap's root
6. Return MAX

Example: inserting P4 with priority 1 into the heap above. (PQ_INSERT, Steps 1-3) It is placed at the next open slot, index 3:

(Step 4) i = 3 > 0, so the loop runs: parent = (3-1)/2 = 1, whose priority is 4. Since A[parent].priority = 4 >= A[i].priority = 1, the If condition holds and the loop breaks: no swap is needed, and P4 stays a leaf.

Example: PQ_DELETE_MAX. (Step 1) N = 4 != 0, so there is no underflow. (Step 2) Save the root, MAX = A[0], which is P2 with priority 5. (Step 3) Move the last element, A[N-1], which is P4 with priority 1, to the root. (Step 4) Shrink the heap: N = 3:

(Step 5) Call HEAPIFY_DOWN(A, 3, 0): compare P4 (priority 1) with its two children, P3 (priority 4) and P1 (priority 2), and swap with the larger, P3:

P4 (now at index 1) has no children within the current heap size, so the process stops. (Step 6) P2 with priority 5 has been returned, and the heap correctly holds P3 with priority 4 as the new maximum.

Time complexity summary

Quick recall

• Priority queue: removes elements by priority, not arrival order (unlike a plain FIFO queue).
• Operations: insert, peek (highest/lowest), delete (highest/lowest).
• A binary heap is the standard implementation: max heap → max-priority queue, min heap → min-priority queue.
• Peek is O(1) (the extreme is always at the root); insert and delete are O(log n).
• "Priority queue" names the behavior; "heap" names the structure that implements it efficiently, the same way "stack" and "array/linked-list" are separate layers.