Python Heap and Priority Queue: A Beginner’s Guide

You keep re-sorting your list every time you need the smallest or largest item. Every time a new task arrives, you call sort() again. It works — but it is O(n log n) on every insert. There is a data structure designed to do this in constant time, and Python ships with it built in. The heap is one of the most useful tools in a programmer’s toolkit, and understanding it will level up how you think about ordering, scheduling, and selection problems.

In this tutorial, you will learn to:

• Understand what a heap is and how a min-heap organises data
• Use Python’s heapq module to create and manipulate heaps
• Build a priority queue on top of a heap in pure Python
• Apply heaps to real problems: task scheduling, k-way merges, and top-k selection
• Avoid the common mistakes that make heaps behave unexpectedly

What Is a Heap?

A heap is a binary tree where every parent node is smaller than or equal to its children (min-heap) or larger than or equal to its children (max-heap). The defining property is that the smallest (or largest) element is always at the root — accessible in O(1) time. The tree is complete, meaning it fills left-to-right at every level, which keeps the height logarithmic: O(log n) for insert and extract operations.

Heaps are not sorted in the traditional sense. What they guarantee is that the root is the minimum (or maximum) and that the heap property is maintained after every insertion or deletion. This makes them ideal for priority queue implementations, where you repeatedly need to access and remove the highest-priority item.

Prerequisites

This article assumes you are comfortable with Python lists and basic list operations. Familiarity with the concept of O(n) and O(log n) time complexity will help, but is not required. No prior knowledge of trees is needed — we represent the heap internally as a flat list.

How a Min-Heap Works Internally

Python’s heapq implements a min-heap using a plain list. The tree structure is implicit: for any index i, its children are at 2*i + 1 and 2*i + 2, and its parent is at (i - 1) // 2. The heap property means each element is ≤ its children.

# Visualising the list-index-to-tree mapping
# heap = [10, 20, 30, 40, 50, 60, 70]
#
#              10          ← index 0, root
#            /    
#          20      30     ← indices 1, 2
#         /      /  
#       40   50 60   70  ← indices 3, 4, 5, 6
#
# Parent of index i:  (i - 1) // 2
# Children of index i:  2*i + 1, 2*i + 2

When you insert an element (heappush), it is added at the end and “bubbled up” until the heap property is restored. When you remove the root (heappop), the last element moves to the root and “sinks down” — swapping with the smaller child at each step until the heap property holds. Both operations are O(log n).

Python’s heapq Module

Python’s standard library includes heapq — a compact module with exactly the operations you need. It is available in every Python installation with no extra dependencies.

Creating a Heap

There are two ways to create a heap. The fastest is heapify, which converts any list into a valid heap in O(n) time — faster than inserting elements one by one.

import heapq

# Method 1: heapify an existing list
numbers = [40, 10, 30, 20, 50]
heapq.heapify(numbers)
print(numbers)  # [10, 20, 30, 40, 50]

# Method 2: build an empty heap and push items
heap = []
heapq.heappush(heap, 25)
heapq.heappush(heap, 5)
heapq.heappush(heap, 17)
print(heap)  # [5, 17, 25]

Push and Pop

heappush inserts an element while maintaining the heap property. heappop removes and returns the smallest element. Use heappop when you need to drain items in sorted order.

import heapq

heap = []
heapq.heappush(heap, 8)
heapq.heappush(heap, 3)
heapq.heappush(heap, 12)
heapq.heappush(heap, 1)

print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 3
print(heapq.heappop(heap))  # 8
print(heapq.heappop(heap))  # 12

Peek Without Removing

The root element is always at index 0. Access it directly without modifying the heap.

import heapq

heap = [4, 7, 2, 9, 1]
heapq.heapify(heap)

smallest = heap[0]  # O(1) — no modification
print(smallest)  # 1

Replace: Pop Then Push in One Step

heapreplace removes and returns the root, then pushes a new element. It is one operation rather than two — useful when you want to maintain a fixed-size heap of “top k” items.

import heapq

heap = [1, 3, 7, 9]
heapq.heapify(heap)

smallest = heapq.heapreplace(heap, 2)
print(smallest)  # 1 — the old root
print(heap)      # [2, 3, 7, 9] — heap property maintained

The Priority Queue Problem

A priority queue is an abstract data type where items have a priority, and the item with the highest priority (lowest number in a min-heap, or highest in a max-heap) is served first. Heaps are the most common internal representation because they support O(log n) insertion and O(1) access to the top-priority item.

Python does not have a built-in PriorityQueue class in the standard library for general use — the queue module provides one, but it is thread-safe and slower. For single-threaded use, a heap-based implementation using heapq is the idiomatic choice.

Building a Priority Queue with heapq

The key insight is that heapq compares tuples element-by-element. By storing (priority, task) tuples, Python automatically compares by the first element — the priority. Lower numbers mean higher priority.

import heapq

class PriorityQueue:
    def __init__(self):
        self._heap = []
        self._counter = 0  # tiebreaker for equal priorities

    def push(self, item, priority):
        # (priority, counter, item) — counter breaks ties without TypeError
        heapq.heappush(self._heap, (priority, self._counter, item))
        self._counter += 1

    def pop(self):
        if not self._heap:
            raise IndexError("pop from empty priority queue")
        return heapq.heappop(self._heap)[2]

    def peek(self):
        if not self._heap:
            raise IndexError("peek from empty priority queue")
        return self._heap[0][2]

    def __len__(self):
        return len(self._heap)

    def __bool__(self):
        return bool(self._heap)


# Example: task scheduler
pq = PriorityQueue()
pq.push("send report", 2)       # low priority
pq.push("reply to email", 1)     # high priority
pq.push("fix critical bug", 0)   # urgent — highest priority
pq.push("review PR", 1)          # same priority as reply — order preserved by counter

print(pq.pop())   # fix critical bug
print(pq.pop())   # reply to email
print(pq.pop())   # review PR — added after reply but same priority
print(pq.pop())   # send report

heapq vs queue.PriorityQueue

Feature	heapq (list-based)	queue.PriorityQueue
Thread-safe	No	Yes
Speed	Faster (no locking)	Slower (mutex overhead)
Best for	Single-threaded, batch processing	Multi-threaded producers/consumers
API	Functional: push/pop functions	Object-oriented: put/get methods

Practical Example: Top-K Problems

A common use of heaps is finding the k largest or k smallest elements in a stream or large dataset without sorting the entire collection. The strategy: maintain a heap of size k. As new items arrive, use heapreplace to keep only the k most relevant.

import heapq

def top_k(items, k):
    """Return the k largest elements, keeping a heap of size k."""
    if k <= 0:
        return []
    heap = []
    for item in items:
        if len(heap)  heap[0]:
            heapq.heapreplace(heap, item)
    # heap now contains the k largest — return sorted descending
    return sorted(heap, reverse=True)


scores = [37, 29, 61, 14, 82, 95, 11, 73, 44, 68]
print(top_k(scores, 3))   # [95, 82, 73]
print(top_k(scores, 5))   # [95, 82, 73, 68, 61]

Practical Example: K-Way Merge

Given k sorted lists, merge them into a single sorted list efficiently. A naive approach merges two lists at a time — O(k n). A heap-based k-way merge runs in O(n log k), making it significantly faster for large k.

import heapq

def kway_merge(*sorted_lists):
    """Merge multiple sorted lists into one sorted list using a heap."""
    result = []
    # Seed the heap with (value, list_index, element_index)
    heap = []
    for i, lst in enumerate(sorted_lists):
        if lst:  # skip empty lists
            heapq.heappush(heap, (lst[0], i, 0))

    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        # Push the next element from the same list
        next_idx = elem_idx + 1
        if next_idx < len(sorted_lists[list_idx]):
            next_val = sorted_lists[list_idx][next_idx]
            heapq.heappush(heap, (next_val, list_idx, next_idx))

    return result


list1 = [1, 5, 9]
list2 = [2, 6, 10]
list3 = [3, 7, 11]

merged = kway_merge(list1, list2, list3)
print(merged)  # [1, 2, 3, 5, 6, 7, 9, 10, 11]

When to Use a Max-Heap

Python’s heapq only provides a min-heap. But you can invert priorities to simulate a max-heap. Simply store negated values — the most negative number becomes the largest.

import heapq

# Simulate a max-heap by negating priorities
max_heap = []
heapq.heappush(max_heap, (-10, "task A"))
heapq.heappush(max_heap, (-30, "task B"))
heapq.heappush(max_heap, (-5, "task C"))

# heappop gives us the most negative (i.e. largest original) value
priority, task = heapq.heappop(max_heap)
print(f"Highest priority: {task} (priority={-priority})")
# Output: Highest priority: task B (priority=30)

Common Mistakes and Gotchas

• A heap is not a sorted list. The heap property only guarantees the root is the minimum. Iterating over a heap does not produce sorted output. If you need a sorted list, call sorted(heap) after heapifying, or drain it with heappop.
• Tuple comparison catches new Python users. When two items have the same priority, heapq compares the second element. If that element is not comparable (e.g., mixing int and str), you get a TypeError. Use a tiebreaker as a third tuple element: (priority, counter, item).
• Negative indices do not work. The parent/child formulas (2*i+1, etc.) assume standard list indexing. Python’s negative indexing does not apply here — it will give wrong results.
• heapreplace returns the old root first. This is different from popping then pushing separately. If you need the new element to be included in the comparison (e.g., for top-k), use heapreplace. If you want to ensure an element is always in the heap after replacement, the order matters.
• The list is modified in place. heapq.heapify() reorders the list in-place. If you need the original order elsewhere, work on a copy.

Summary and Next Steps

You now understand what a heap is, how Python’s heapq module implements a min-heap on a flat list, and how to build a priority queue on top of it. You have seen practical applications: top-k selection, k-way merging, and task scheduling. You also know the common pitfalls — tuple comparison edge cases, the “heap is not sorted” gotcha, and how to simulate a max-heap by negating priorities.

To continue learning, explore these related topics:

• Level Order Tree Traversal — the heap’s binary tree structure appears in tree breadth-first traversal too
• Python Lists for Beginners — the underlying data structure that powers heapq

Frequently Asked Questions

Is heapq a min-heap or a max-heap?

heapq is a min-heap — the smallest element is always at the root (index 0). To simulate a max-heap, store negated values: heapq.heappush(heap, -x) and -heapq.heappop(heap).

What is the time complexity of heapq operations?

heappush and heappop are both O(log n). heapify is O(n) — linear time to build a heap from an existing list. Accessing the root element at heap[0] is O(1).

When should I use a heap instead of sorting?

Use a heap when you have a dynamic stream of items and need to repeatedly find the smallest or largest — for example, a task scheduler, a top-k monitor, or merging sorted streams. If you just need the sorted result of a fixed collection, sorted() is simpler and often faster. Heaps shine when data arrives incrementally.