A heap is a specialized tree-based structure that always keeps the smallest (or largest) value easy to grab in O(1) time, while still supporting O(log n) insertion and removal. It's the structure behind priority queues — queues where items are served by priority rather than by arrival order, like a hospital triage system instead of a ticket line.

A heap isn't sorted the way a binary search tree is — it only guarantees a much looser invariant, which is exactly what makes it faster to maintain.

Min-Heap vs Max-Heap

A min-heap enforces that every parent node is smaller than or equal to both of its children — so the smallest value in the whole structure is always sitting at the root. A max-heap is the mirror image: every parent is larger than its children, so the maximum is always at the root. Note this says nothing about the relationship between siblings or across different branches — only parent-to-child, which is why a heap is much cheaper to maintain than a fully sorted structure.

The Array-Based Representation

Heaps are almost always implemented as a plain array rather than a linked tree of node objects, because a complete binary tree (every level full except possibly the last, filled left to right) maps perfectly onto array indices with simple arithmetic — no pointers needed at all:

# For a node at index i (0-based array):
def parent(i):
    return (i - 1) // 2

def left_child(i):
    return 2 * i + 1

def right_child(i):
    return 2 * i + 2

# heap = [1, 3, 2, 7, 4, 5]  represents this tree:
#            1
#          /   \
#         3     2
#        / \   /
#       7   4 5

This is only possible because a heap is always a complete tree — no gaps anywhere except possibly trailing slots on the last level — which guarantees the index math always lands on a valid, predictable position.

Insert and Extract: O(log n)

Inserting adds the new value at the next open array slot, then repeatedly swaps it with its parent ("sifts up") until the heap property is restored. Extracting the min (or max) removes the root, moves the last element into its place, then repeatedly swaps it with the smaller child ("sifts down") until the property holds again. Both operations only ever move along a single path from root to leaf or leaf to root, which is why each one costs O(log n) — proportional to the height of the tree, exactly like a balanced AVL tree, but without AVL's rotation logic.

Using Python's heapq Module

In practice you rarely implement a heap from scratch — Python's standard library ships one in the heapq module, which operates directly on a plain list and is always a min-heap by convention.

import heapq

tasks = []
heapq.heappush(tasks, (3, "write report"))
heapq.heappush(tasks, (1, "fix critical bug"))
heapq.heappush(tasks, (2, "reply to emails"))

# Always pops the lowest-priority-number item first
while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"{priority}: {task}")

Output:

1: fix critical bug
2: reply to emails
3: write report

To simulate a max-heap with heapq, the common trick is negating the values on the way in and out. Priority queues built on heaps show up constantly in real algorithms — Dijkstra's shortest path algorithm, task schedulers, and event-driven simulations all lean on exactly this "always grab the smallest next" behavior.