Priority Queue (Binary Heap) Visualization

The problem: always serve the most urgent item next

A priority queue holds items that each have a priority. Items arrive in any order, but they leave in order of priority: a min-priority queue always hands out the item with the smallest priority number (think "1 = most urgent"), a max-priority queue the largest. An ordinary queue is the special case where the priority is the arrival time.

The operations are:

• enqueue(item, priority) (also called insert or push): add an item.
• peek() (also top or find-min): return the best item without removing it.
• dequeue() (also extract-min or pop): remove and return the best item.
• changePriority(item, p) (decrease-key / increase-key): give an item that is already queued a new priority.

A sorted array makes dequeue cheap but enqueue cost O(n), because everything after the new item has to shift. An unsorted array is the other way round. A binary heap makes every operation O(log n) or better, which is why almost every library priority queue is one. This page animates the queue operations on a heap; the Heap page shows the heap on its own.

The idea: a complete binary tree stored in an array

A binary heap is a binary tree with two rules:

• Shape: the tree is complete. Every level is full except maybe the last, which fills from the left. So a heap of n items has height ⌊log₂ n⌋.
• Heap property: no item has a better priority than its parent. In a min-heap every parent is ≤ its children, so the minimum is at the root.

Because the tree is complete, it needs no pointers: store it level by level in an array. With 0-based indexes, the node at index i has its parent at ⌊(i − 1) / 2⌋ and its children at 2i + 1 and 2i + 2. The animation shows both views at once: the array on top, the same items as a tree below, with the index of every slot in blue.

Only the path from a node to the root is ordered. Siblings, cousins and whole subtrees are in no particular order, which is exactly why a heap is cheaper to maintain than a sorted array.

The algorithm

// better(a, b): a.priority < b.priority for a min-queue, > for a max-queue

enqueue(item):
    heap[size] = item                   // next free slot = next leaf
    pos[item] = size
    size = size + 1
    siftUp(size - 1)

peek():
    return heap[0]

dequeue():
    top = heap[0]
    size = size - 1
    heap[0] = heap[size]                // last leaf fills the hole at the root
    pos[heap[0]] = 0
    delete pos[top]
    if size > 0: siftDown(0)
    return top

changePriority(item, p):
    i = pos[item]                       // O(1): no search
    old = heap[i].priority
    heap[i].priority = p
    if p is better than old: siftUp(i)  else: siftDown(i)

siftUp(i):
    while i > 0 and better(heap[i], heap[parent(i)]):
        swap(i, parent(i))              // swap also updates pos for both items
        i = parent(i)

siftDown(i):
    loop:
        c = the better of i's children (none: stop)
        if not better(heap[c], heap[i]): stop
        swap(i, c)
        i = c

heapify(array):                         // build a heap from n items at once
    for i = size/2 - 1 down to 0:
        siftDown(i)

The pos array (the position map, shown under the tree) records where every item currently sits. It is only needed for changePriority: without it, finding an item would mean scanning the whole heap. A heap with a position map is often called an indexed priority queue.

A worked example

A min-priority queue, starting empty. Items are written name:priority, and the array is listed from index 0.

Operation	What happens	Returns	Array afterwards
enqueue(A, 5)	empty queue: A becomes the root		A:5
enqueue(B, 3)	B goes to index 1; 3 < 5 (its parent A), so they swap		B:3, A:5
enqueue(C, 8)	C goes to index 2; 8 is not smaller than its parent B:3, so it stays		B:3, A:5, C:8
enqueue(D, 1)	D goes to index 3; swaps with A:5 (index 1), then with B:3 (index 0)		D:1, B:3, C:8, A:5
dequeue()	take D:1; the last item A:5 moves to the root; its smaller child is B:3, so they swap	D:1	B:3, A:5, C:8
changePriority(C, 2)	pos[C] = 2; 2 is better than 8, so sift up: 2 < 3, swap with B		C:2, A:5, B:3
dequeue()	take C:2; B:3 moves to the root; its only child A:5 is not smaller, so it stays	C:2	B:3, A:5

The items came out as D:1, C:2, and B:3 would be next: in priority order, not arrival order. Notice that C overtook B and A only because its priority changed while it waited.

Why it is correct

Each operation breaks the heap property in at most one place and then repairs it along a single path.

• Sift up. A new leaf, or an item whose priority improved, may be better than its parent, but everything below it is still fine: its old children were no better than the old value, so they are no better than the new, better one. Swapping it with its parent moves the problem one level up. It stops at the root or at a parent that is at least as good, and then the property holds everywhere.
• Sift down. After a dequeue (or a worse priority), the item at i may be worse than a child. Swapping it with the better of its two children is essential: that child becomes the parent of the other child, and since it was the better of the two, the property holds on both sides. The problem moves one level down, until the item is at a leaf or no child is better.
• Heapify. Leaves are heaps of one item. Going from the last node that has a child back to the root, both subtrees of i are already heaps when i is sifted down, so afterwards the subtree at i is a heap. At the root, the whole array is one.

The shape rule is kept automatically: enqueue adds exactly the next leaf, dequeue removes exactly the last one, and swaps never change the shape.

Time and space

Operation	Binary heap	Sorted array	Unsorted array
enqueue	O(log n)	O(n)	O(1)
peek	O(1)	O(1)	O(n)
dequeue	O(log n)	O(1)	O(n)
changePriority (with a position map)	O(log n)	O(n)	O(1)
build from n items	O(n)	O(n log n)	O(n)

Sift up and sift down do at most one swap per level, and the tree has ⌊log₂ n⌋ levels below the root. Heapify is O(n), not O(n log n): half the nodes are leaves and never move, a quarter can move at most one level, an eighth at most two, and the sum n(1/4 + 2/8 + 3/16 + ...) is less than n. The space is one array slot per item, plus one position-map entry per item if changePriority is needed.

Common mistakes, edge cases and variants

• Swapping with the wrong child in sift down. Always compare with the better child. Swapping with the other one puts a worse item above a better one.
• Off-by-one parent and child formulas. 0-based arrays use (i − 1)/2, 2i + 1 and 2i + 2. Many textbooks (and the Heap page) leave index 0 empty and use i/2, 2i and 2i + 1.
• Forgetting the position map during swaps. Every swap must update pos for both items, or changePriority later edits the wrong slot.
• Ties are not first-in first-out. A heap is not stable: two items with equal priority can come out in either order. If order matters, break ties with an arrival counter, as Python's documentation suggests for heapq.
• Libraries without decrease-key. Java's PriorityQueue, C++'s std::priority_queue and Python's heapq have no position map. The usual workaround in Dijkstra's algorithm is lazy deletion: push the item again with its new priority and skip stale copies when they are dequeued.
• Max from a min-heap. Libraries that only offer one order can be used for the other by negating the priorities (Python's heapq is min-only; C++'s priority_queue is max by default).
• Other heaps. A d-ary heap (more children per node) makes enqueue and decrease-key cheaper and dequeue dearer. Binomial queues, leftist heaps and skew heaps can merge two queues quickly, and Fibonacci heaps make decrease-key O(1) amortised.

Where priority queues are used

Shortest paths and spanning trees: Dijkstra's algorithm, A* and Prim's algorithm all repeatedly dequeue the closest vertex and decrease the keys of its neighbours. Huffman coding repeatedly merges the two lightest trees. Heap sort is heapify followed by n dequeues. Beyond algorithms courses, priority queues schedule processes and timers in operating systems, order events in discrete-event simulations, merge k sorted files in external sorting, keep the top k items of a data stream, and pick the next request by deadline in network routers and job queues.

References

Priority queue

Binary heap