Learn how heaps maintain instant access to the minimum or maximum element, and how they power priority queues.

Heap

A heap is a binary tree with one ordering rule, weaker than a BST: every parent must be smaller than its children (min-heap) or larger than its children (max-heap). Unlike a BST, there is no rule comparing siblings or left vs right — only parent vs child.

This relaxed rule is exactly what makes heaps so fast at one specific job — always knowing the minimum (or maximum) element instantly.

Min-heap:                    Max-heap:
       5                          50
      / \                        /  \
     8   10                    30    40
    / \                       / \
   20  15                   10   25

Every parent ≤ children      Every parent ≥ children

Min-Heapparent ≤ children · 5 nodes

underlying array — parent(i) = (i−1)//2 · left(i) = 2i+1 · right(i) = 2i+2

[0]

[1]

[2]

[3]

[4]

Insert or extract-min to see the heap rebalance

Heaps are stored as arrays, not pointer trees

Because a heap is always a complete tree (every level filled except possibly the last, filled left to right), it can be stored compactly in an array — no left/right pointers needed.

Array:  [5, 8, 10, 20, 15]
Index:   0  1   2   3   4

For any node at index i:
  left child  = 2i + 1
  right child = 2i + 2
  parent      = (i - 1) // 2

       5  (index 0)
      / \
     8   10   (index 1, 2)
    / \
  20   15     (index 3, 4)

Insert — bubble up

Add the new value at the end of the array, then swap it upward with its parent until the heap property is restored.

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def insert(self, value):
        self.heap.append(value)          # add at the end
        self._bubble_up(len(self.heap) - 1)

    def _bubble_up(self, i):
        while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
            # swap with parent if smaller
            self.heap[i], self.heap[self.parent(i)] = (
                self.heap[self.parent(i)], self.heap[i]
            )
            i = self.parent(i)

Extract min — bubble down

The minimum is always at index 0. Remove it, move the last element to the root, then swap it downward with its smaller child until the heap property is restored.

    def extract_min(self):
        if not self.heap:
            return None

        min_value = self.heap[0]
        last = self.heap.pop()

        if self.heap:
            self.heap[0] = last
            self._bubble_down(0)

        return min_value

    def _bubble_down(self, i):
        n = len(self.heap)
        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            smallest = i

            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right

            if smallest == i:
                break   # heap property restored

            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            i = smallest

Why insert and extract are O(log n)

A heap is always a complete tree, so its height is always log n — never degenerates like an unbalanced BST can. Bubbling up or down only ever travels the height of the tree, one level at a time.

n = 1,000,000 elements
height = log₂(1,000,000) ≈ 20

insert and extract_min both take at most 20 swaps.

Python's built-in — heapq

Python's standard library has heapq — a min-heap built directly on top of a regular list.

import heapq

nums = [5, 8, 10, 20, 15]
heapq.heapify(nums)         # convert list into a heap in-place — O(n)

heapq.heappush(nums, 3)     # insert — O(log n)
smallest = heapq.heappop(nums)   # extract min — O(log n)
print(nums[0])               # peek min — O(1), always at index 0

For a max-heap, Python has no built-in — negate the values:

nums = [5, 8, 10, 20, 15]
max_heap = [-x for x in nums]
heapq.heapify(max_heap)

largest = -heapq.heappop(max_heap)   # negate back to get the real max

Real use case — priority queue

A heap is the standard way to implement a priority queue — items are processed by priority, not insertion order.

import heapq

tasks = []
heapq.heappush(tasks, (3, "low priority email"))
heapq.heappush(tasks, (1, "server is down"))
heapq.heappush(tasks, (2, "user reported bug"))

while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"[{priority}] {task}")

# [1] server is down
# [2] user reported bug
# [3] low priority email

The tuple's first element becomes the sort key — lower numbers come out first.

Real use case — top K elements

Heaps efficiently solve "find the K largest/smallest" without sorting the entire collection.

import heapq

nums = [3, 1, 4, 1, 5, 9, 2, 6]

top_3_largest = heapq.nlargest(3, nums)    # [9, 6, 5]
top_3_smallest = heapq.nsmallest(3, nums)  # [1, 1, 2]

nlargest/nsmallest use a heap internally — O(n log k) instead of O(n log n) for a full sort, which matters when k is much smaller than n.

Heap vs BST

	Heap	BST
Ordering rule	Parent vs children only	Left < parent < right, fully ordered
Find min/max	O(1)	O(log n) — walk to leftmost/rightmost
Search arbitrary value	O(n)	O(log n)
Storage	Array (compact)	Pointer-based nodes
Always balanced	Yes (complete tree)	No — needs self-balancing variant
Use case	Priority queue, top K	Sorted search, range queries

Choose a heap when you only ever need the min or max — never an arbitrary search. Choose a BST when you need to search, range-query, or retrieve sorted order. They solve different problems despite both being binary trees.

Complexity

Operation	Time
Peek min/max	O(1)
Insert	O(log n)
Extract min/max	O(log n)
Heapify (build from array)	O(n)
Search arbitrary value	O(n)

Heap

On this page