Priority Queue Visualizer — Binary Heap Implementation

Q: How do you make a max priority queue in Python?

heapq only provides a min-heap, so push negated priorities — heappush(h, (-priority, item)) — and negate again after heappop. For non-numeric keys, wrap items in a class whose __lt__ compares in reverse.

What is a priority queue?

A priority queue is an abstract data type in which every element has a priority and the next element served is always the one with the highest priority — or the lowest, in a min-priority queue — rather than the one that arrived first. It is almost always implemented with a binary heap, which gives O(1) peek and O(log n) insert and extract, and it powers Dijkstra's shortest paths, event schedulers, Huffman coding and top-k queries.

How it works

insert(x) (push): append x at the end of the heap array and sift it up while it has higher priority than its parent. O(log n).
peek(): return the root a[0] without removing it. O(1).
extract() (pop): remember the root, move the last element into its place, shrink the array and sift the new root down. O(log n).
change priority: overwrite an element's key, then sift it up if its priority rose or down if it fell. O(log n) when you know its index.

Priority queue vs queue vs heap

A queue serves elements in arrival order (FIFO); a stack serves the newest first (LIFO). A priority queue generalises both: each element carries a priority and the queue always serves the best one. Use each element's arrival time as its priority and you get a queue back; use the negative arrival time and you get a stack.

"Priority queue" names the interface — insert, peek, extract — while a heap is its most common implementation. The two words are often used interchangeably, but a priority queue can also be built on a sorted array, a balanced search tree or one of the more exotic heaps.

Implementation choices compared

Unsorted array or list: insert O(1), extract O(n) — every extraction scans for the best element.
Sorted array: extract O(1) from the end, insert O(n) — elements shift to make room.
Balanced BST: insert and extract O(log n), plus ordered iteration, but with pointers and rebalancing overhead.
Binary heap: O(1) peek, O(log n) insert and extract, O(n) to build from a batch, all in one compact array — the default choice.
d-ary, pairing and Fibonacci heaps: tuned variants. A Fibonacci heap makes decrease-key O(1) amortised, which improves Dijkstra's theoretical bound to O(E + V log V), although binary heaps are usually faster in practice.

Worked example: serving the smallest key first

This page opens with a min-priority queue holding 35, 12, 48, 7, 61, 23, 9, 54, 18, 40 — think of them as minutes until each task is due. As a min-heap the array is [7, 12, 9, 18, 40, 23, 48, 54, 35, 61], and an extract-min is ready to play:

The answer is the root: 7, the most urgent task.
The last element, 61, moves into the root and the heap shrinks to nine elements: [61, 12, 9, 18, 40, 23, 48, 54, 35].
Sift down: 61's children are 12 and 9; the smaller is 9, so they swap. At index 2 its children are 23 and 48; it swaps with 23.
61 is now a leaf, so the heap is valid again: [9, 12, 23, 18, 40, 61, 48, 54, 35].

Two swaps, and the next task — 9 — is already waiting at the root. An insert is the mirror image: add the new key at the end and let it climb while it is smaller than its parent.

Where priority queues are used

Dijkstra's shortest paths and A* search: the queue holds (distance, vertex) pairs and always expands the closest unsettled vertex. With a binary heap Dijkstra runs in O((V + E) log V).
Prim's minimum spanning tree: repeatedly take the cheapest edge leaving the tree.
Schedulers and timers: run the job with the earliest deadline or highest priority next. Java's ScheduledThreadPoolExecutor and the Go runtime's timers both keep pending work in a heap.
Event-driven simulation: process events in timestamp order, inserting new future events as you go.
Huffman coding: repeatedly merge the two least frequent symbols.
Top-k and streaming: keep the k largest items seen so far in a min-heap of size k (O(n log k)), track a running median with two heaps, or merge k sorted lists by always taking the smallest head.

Priority queues in Python, Java and C++

Python: heapq turns a plain list into a min-heap — heappush, heappop, heapify (O(n)) and nsmallest/nlargest. queue.PriorityQueue wraps it with locking for threads.
Java: java.util.PriorityQueue is a min-heap by default; pass Comparator.reverseOrder() for a max-heap.
C++: std::priority_queue is a max-heap by default; declare std::priority_queue<int, std::vector<int>, std::greater<int>> for a min-heap.

Heaps are not stable: two items with equal priority can come out in either order. When ties must be served first-come-first-served — or when the payloads cannot be compared — push (priority, counter, item) tuples with an increasing counter.

Common mistakes

Iterating over the heap and expecting sorted order. Only the root is in order; pop repeatedly to get a sorted sequence.
Changing an element's priority in place without sifting it, which silently breaks the heap. Either re-sift from its index, or push the updated entry and skip stale ones when they are popped — the usual "lazy deletion" trick for Dijkstra with heapq.
Comparing payloads on ties. In Python, comparing (3, {"job": 1}) with (3, {"job": 2}) raises TypeError; add a counter as the second tuple field.
Assuming the library default. Python and Java give you a min-heap, C++ a max-heap.

Time and space complexity

Case	Time	Space	Why
peek	O(1)	O(1)	The highest-priority element is the root.
insert / push	O(log n)	O(1)	Sift-up along one leaf-to-root path.
extract / pop	O(log n)	O(1)	Sift-down along one root-to-leaf path.
change priority	O(log n)	O(1)	Re-sift from the element's index; finding the element first is O(n) without an index map.
build from n items	O(n)	O(1)	Bottom-up heapify instead of n separate inserts.
Storage	—	O(n)	One array slot per element, no pointers.

Priority Queue in Python

def peek_min(a):
    if not a:
        raise IndexError("empty heap")
    return a[0]  # the root, O(1)


def insert(a, key):
    a.append(key)  # a[n] ← key;  n ← n + 1
    sift_up(a, len(a) - 1)


def sift_up(a, i):
    # move a[i] up while it beats its parent
    while i > 0:
        p = (i - 1) // 2
        if a[p] <= a[i]:  # in order
            return
        a[i], a[p] = a[p], a[i]
        i = p


def extract_min(a):
    if not a:
        raise IndexError("empty heap")
    top = a[0]
    # swap(a[0], a[n − 1]);  n ← n − 1
    a[0], a[-1] = a[-1], a[0]
    a.pop()
    sift_down(a, 0, len(a))
    return top


def sift_down(a, i, n):
    # sink a[i] inside the heap a[0:n]
    while 2 * i + 1 < n:
        l, r = 2 * i + 1, 2 * i + 2
        smallest = l
        if r < n and a[r] < a[l]:
            smallest = r
        if a[i] <= a[smallest]:  # in order
            return
        a[i], a[smallest] = a[smallest], a[i]
        i = smallest

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Is a priority queue the same as a heap?

Not exactly. A priority queue is the abstract interface (insert, peek, extract the best element); a binary heap is the data structure most often used to implement it. The same interface could sit on a sorted array or a balanced BST, just with different costs.

What is the time complexity of a priority queue?

With a binary heap: O(1) to peek, O(log n) to insert, O(log n) to extract the top element and O(n) to build one from n items. Searching for an arbitrary element is O(n).

Why does Dijkstra's algorithm use a priority queue?

Dijkstra repeatedly picks the unvisited vertex with the smallest tentative distance. A min-priority queue returns it in O(log V) instead of scanning all vertices in O(V), bringing the total from O(V²) down to O((V + E) log V) on sparse graphs.

How do you make a max priority queue in Python?

heapq only provides a min-heap, so push negated priorities — heappush(h, (-priority, item)) — and negate again after heappop. For non-numeric keys, wrap items in a class whose __lt__ compares in reverse.

Does a priority queue keep FIFO order for equal priorities?

No. Heap operations can reorder elements with equal priority. If ties must be served first-come-first-served, store (priority, sequence_number, item) so the sequence number breaks ties.

What is decrease-key in a priority queue?

An operation that raises an element's priority (lowers its key in a min-heap) and sifts it up to its new place in O(log n). It needs the element's index, so implementations keep a map from item to position; many Dijkstra implementations avoid it by pushing duplicates instead.

Keep learning

Last updated 19 October 2026