# Heaps and Priority Queues

A partially ordered tree giving cheap access to the minimum or maximum element, used wherever you repeatedly need the next-best item.

**Rests on:** Binary Tree Traversal

*Machine Learning · Data Structures*


## Why learn this

You are about to meet a tool that any system relying on speed and urgency depends upon. Once you can build one, you can manage situations where the 'most important' item needs to be handled instantly, while new items arrive continuously. This is what makes a route-finding app quickly identify the next best hop between cities, how a hospital decides which patient to see next based on severity rather than arrival time, and how a computer's operating system decides which program deserves the CPU's attention right now. You will also see how these structures keep track of information efficiently: while they do not sort everything perfectly, they keep the most critical piece of data accessible immediately, which saves enormous amounts of time compared to scanning a long unsorted list.


## The intuition

Imagine you are managing a queue of tasks, and your only goal is always to complete the single most urgent task next. If you kept these tasks in a standard list in random order, you would have to look at every single item to find the most urgent one. This takes longer as your list grows; if you had 100 tasks, you might have to check 100 items to find the top priority. If you kept the list perfectly sorted from start to finish, finding the most urgent task would be instant, but adding a new task and re-sorting the entire list every time would be very slow and tedious.

A heap solves this by using a specific shape: it organizes the tasks into a tree-like structure that is always completely filled from left to right, except possibly for the last level. In this structure, there is one strict rule: the most urgent task (the 'peak' or 'valley') must always sit at the very top node, which we will call the root. The rest of the tasks below it only need to follow a looser rule: every task must be less urgent (or more urgent, depending on your goal) than its own parent above it. 

Because the most urgent item is always at the top, you can access it instantly, regardless of how many tasks you have. When you remove that top task, you do not re-sort the whole list. Instead, you take the last task in the tree, place it at the top, and let it 'bubble down' or 'sink down' by swapping with its most urgent child until the rules are satisfied again. This path is short—specifically, it grows slowly as the number of tasks increases. For example, even if you have a million tasks, the height of this tree is only about 20 steps. So, finding the top item takes one step, and adding or removing an item takes about 20 steps, no matter how huge the list becomes.

Let's look at concrete numbers. Suppose you have 7 tasks with urgency scores: [5, 3, 8, 1, 4, 9, 2]. You want the highest score on top. You arrange them in a complete binary tree (filled left to right):

      8
    /   \
   5     9
  / \   /
 3   4 2

Wait, 9 is greater than its parent 5? No, 9 is the child of 5. Let's rebuild properly for a max-heap (highest score on top):

      9
    /   \
   8     5
  / \   /
 3   4 2

Here, 9 is at the root (top). Its children are 8 and 5. Both 8 and 5 are smaller than 9. Their children are 3, 4, and 2, all smaller than their respective parents. If a new task with score 10 arrives, you place it at the next available spot, then swap it up: 10 swaps with 9, becoming the new root. This took two swaps. If you remove the top (10), you move the last item (2) to the top and let it sink down. It swaps with 8, then with 5, taking a few steps. The key insight is that you only ever touch a small fraction of the items, proportional to the height of the tree, not the total number of items.


## An analogy

Think of a hierarchical company where every manager reports to one boss, and every employee has at most two direct reports (a left report and a right report). The rule of the company is simple: a manager must always have a higher performance score than either of their direct reports. This ensures that the best performer in any department is sitting at the top of that department's hierarchy.

When a new star employee joins, they start at the bottom floor. If their score is higher than their immediate boss's, they swap places, becoming the new boss. They keep moving up until their score is lower than or equal to their new boss. This process is like climbing a ladder rung by rung. Because each department is structured efficiently, no one has to climb more than a few rungs, even if the company is massive.

When the CEO (the absolute top performer) retires, they are replaced by the employee at the very bottom-right of the entire company hierarchy. That person might not be qualified for the CEO role immediately. So, they look at their two direct reports (their new 'subordinates' who were previously peers). If either sub-report has a higher score, the replacement swaps with the highest-scoring subordinate. They keep moving down until their score is higher than both of their current reports. 

The analogy breaks down slightly because in a real company, titles and reporting lines rarely change dynamically like this, and employees don't physically swap desks every day. However, the core idea holds: by enforcing a local rule (parent > children), we ensure global access to the top candidate without scanning everyone.


## Definition

A heap is a complete binary tree data structure where every parent node holds an extreme value (either the maximum or minimum) relative to its children, which guarantees that the most urgent item is always available at the root in constant time, while insertion and removal operations take a number of steps proportional to the height of the tree.


## How it connects

You may have studied Binary Search Trees, which are also tree structures but organize data so that left children are smaller and right children are larger; unlike heaps, binary search trees do not guarantee that the extreme value is at the top without searching. You might also recall Priority Queues, which is the abstract concept of a list where you always extract the most urgent item; a heap is one of the most common ways to build a priority queue efficiently under the hood. Additionally, you have encountered sorting algorithms like Merge Sort; while sorting arranges every single item in order, a heap only arranges items enough to keep the top spot filled, which is why it is much faster for tasks where you only need the best item one at a time.


## The mathematics

The mathematics here is mostly arithmetic and a little bit of counting. The branch of mathematics this draws on is discrete mathematics — the study of countable structures like trees and lists — but you will not need any algebra beyond simple multiplication. The core operation is the comparison: to maintain the heap property, you compare a node with its parent or its children, and swap if needed. Each swap is a simple exchange of two numbers. The efficiency of a heap comes from the fact that the number of comparisons grows only with the height of the tree, which is the logarithm of the number of elements. A full binary tree with n nodes has height about log2(n). For example, a heap with 8 elements has height 3 (since 2^3 = 8). Stepping through one insert: you place the new element at the bottom, then compare it with its parent. If it is more extreme, you swap. You repeat until the heap property holds. This is just a series of comparisons and swaps — no complex formulas, just careful counting of how many steps it takes.

For a node at index i (0-based) in the array representation, its left child is at index 2i+1, its right child at 2i+2, and its parent at floor((i-1)/2). The number of steps for insert or extract is at most the height of the tree, which is Θ(log n).


## A worked example

```
Build a min-heap from the empty heap, inserting the numbers 5, 3, 8, 1 in that order.

Step 1: Insert 5 into empty heap → heap: [5]   # The heap is a list where the first element is the root.
Step 2: Insert 3 as left child of 5 → heap: [5, 3]   # Now compare 3 with its parent 5. Since 3 < 5, swap them.
Step 3: After swap → heap: [3, 5]   # Now 3 is the root, and the heap property holds (3 <= 5).
Step 4: Insert 8 as right child of 3 → heap: [3, 5, 8]   # Compare 8 with parent 3. 8 > 3, so no swap needed.
Step 5: Insert 1 as left child of 5 → heap: [3, 5, 8, 1]   # Compare 1 with parent 5. 1 < 5, so swap.
Step 6: After swap → heap: [3, 1, 8, 5]   # Now 1 is the left child of 3. Compare 1 with new parent 3. 1 < 3, so swap again.
Step 7: After second swap → heap: [1, 3, 8, 5]   # Now 1 is the root, and the heap property holds (1 <= 3 and 1 <= 8).

Result: The final min-heap is [1, 3, 8, 5], where the root is 1, the minimum. The list is not fully sorted, but the minimum is at the front.
```


## From scratch, in Python

```python
class MinHeap:
    def __init__(self):
        self.items = []  # start with an empty list

    def insert(self, value):
        # Append at the end (bottom-right of tree)
        self.items.append(value)
        self._bubble_up(len(self.items) - 1)

    def extract_min(self):
        if not self.items:
            return None
        # Swap root with last element, remove last, then sink down
        self.items[0], self.items[-1] = self.items[-1], self.items[0]
        min_val = self.items.pop()
        if self.items:
            self._sink_down(0)
        return min_val

    def peek_min(self):
        return self.items[0] if self.items else None

    def _bubble_up(self, i):
        while i > 0:
            parent = (i - 1) // 2
            if self.items[i] < self.items[parent]:
                self.items[i], self.items[parent] = self.items[parent], self.items[i]
                i = parent
            else:
                break

    def _sink_down(self, i):
        n = len(self.items)
        while True:
            left = 2 * i + 1
            right = 2 * i + 2
            smallest = i
            if left < n and self.items[left] < self.items[smallest]:
                smallest = left
            if right < n and self.items[right] < self.items[smallest]:
                smallest = right
            if smallest != i:
                self.items[i], self.items[smallest] = self.items[smallest], self.items[i]
                i = smallest
            else:
                break
```


## The same thing, with a framework

```python
Python's standard library has `heapq`, which operates on a plain list. For example:

import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 3)
heapq.heappush(h, 8)
print(h[0])       # 3 (peek)
print(heapq.heappop(h))  # 3

Under the hood, `heapq.heappush` does exactly the same append and sift-up that our MinHeap does — it's a procedural version of the same logic, but you manage the list yourself. `h[0]` gives the minimum because the heap property ensures the root is the smallest. For a max-heap, you can push negative values or use `heapq._heapify_max` (though it's not as well-maintained).
```


## What the code does

This is a complete implementation of a min-heap using a Python list. The list is not sorted, but it always has the smallest element at index 0. The `insert` method appends the new value at the end, then calls `_bubble_up` to restore the heap property by comparing with the parent and swapping as needed. `extract_min` takes the root (the smallest), moves the last element to the root, and calls `_sink_down` to push it down to its correct place by repeatedly swapping with the smaller of its two children. `peek_min` simply returns the root without modifying the heap. The helper methods use the array indices: left child = 2*i+1, right child = 2*i+2, parent = (i-1)//2. This is the standard way heaps are represented — as a list, with the tree structure encoded in the indices.


## Common misconceptions

**A heap is a sorted list** — A heap is basically a sorted list, just stored differently.

A heap does not keep elements in sorted order. It only guarantees that the root is the extreme element and each parent is more extreme than its children. Siblings can be in any order. In fact: A heap is a partial order: only the root is guaranteed to be the minimum or maximum. This weaker guarantee is what makes insert and extract faster.

**Heap property must hold for every pair of nodes** — For a min-heap, every node must be smaller than every other node it is connected to in any way.

The heap property only requires that a parent is smaller than its children, not that all nodes in the left subtree are smaller than all in the right subtree. In fact: The heap property is local: each parent must be more extreme than its children. It applies recursively, but does not impose a global ordering.

**Heaps are the same as binary search trees** — A heap is basically a binary search tree with the same shape.

A binary search tree keeps its elements in sorted order for in-order traversal; a heap does not. The heap does not support searching for an arbitrary element quickly — it only gives you the extreme. In fact: A heap is a binary tree, but it is not a search tree. The heap property is different from the binary-search-tree property, and heaps do not support fast lookup of arbitrary values.

**Priority queue only works for numbers** — Priority queues can only hold numbers, because you need to compare them.

Priority queues work with any type that has a notion of priority — strings, objects, tasks with urgency scores. In Python, you can store any object and provide a key or comparator. In fact: A priority queue is generic: the priority can be any easily comparable value. You provide the comparison, and the heap structure handles the rest.

**Extracting the minimum always gives sorted output** — If I repeatedly call extract_min, I'll get a sorted list, so a heap is just a slow way to sort.

While repeatedly extracting the minimum does give sorted output, that is exactly heapsort, and it is O(n log n) — not slower than other sorts. But heaps are not designed for sorting; they are designed for dynamic insertions and extractions of the extreme element. In fact: Heaps can sort (heapsort), but their main purpose is as a dynamic priority queue where you can insert and extract the extreme element efficiently, without sorting the whole collection each time.

**A heap can handle duplicates easily** — Duplicates are a problem because the heap property breaks.

Duplicates are perfectly fine in a heap; the property is a non-strict inequality (≤ or ≥) on each edge, so equal elements can appear anywhere. In fact: The heap property is a non-strict inequality, so equal values can appear without violating anything. The heap does not care which of two equal elements is the 'minimum'.


## In short

A heap is a binary tree stored in an array, where the root always holds the smallest (min-heap) or largest (max-heap) element. It allows you to insert a new element and extract the extreme in logarithmic time, while peeking at the extreme is constant time. The heap property is local — each parent is more extreme than its children — which is weaker than a full sort but much cheaper to maintain. The array representation uses indices: left child at 2i+1, right child at 2i+2, parent at floor((i-1)/2). The two key operations are bubble-up (used on insert) and sink-down (used on extract). Priority queues built from heaps are used everywhere a system repeatedly needs the next-best item: in beam search for language models, top-k retrieval in RAG, A* search in planning agents, and countless scheduling systems.


## Where this is used

Heaps and priority queues show up in AI systems in several key ways. First, in large language models (LLMs) during generation: when the model generates text token by token, it often uses a beam search to keep the top-k most likely partial sequences. A priority queue is used to maintain the top-k candidates efficiently, inserting new candidates and extracting the best one at each step. The heap is the natural structure here because you repeatedly need the 'best' partial sentence, and you want to insert new candidates as you expand. Second, in small language models running on phones or laptops (like on-device assistants), a priority queue can manage a task scheduler that decides which computation to run next based on urgency or resource constraints. Third, in retrieval-augmented generation (RAG), the system must find the most relevant chunks of text to feed to the model. When many chunks are scored against a query, a heap can be used to keep the top-k highest-scoring chunks without sorting the entire collection. The `heapq` module in Python is a common tool for this — a developer writes `heapq.nlargest(k, chunks, key=score)` and the heap does the heavy lifting. Fourth, in agentic systems that plan and call tools, a priority queue is the core of best-first search algorithms like A*. The agent maintains a frontier of possible next states, each with a cost estimate, and repeatedly expands the most promising one. This is exactly what a priority queue provides: the next-best item in log time. Fifth, in everyday applied machine learning, priority queues power event-driven simulations, real-time monitoring dashboards that need to process the most urgent alert first, and network routers that forward packets based on priority. In software practice, a developer rarely implements a heap from scratch — Python's `heapq` module provides array-based heaps, and `queue.PriorityQueue` provides a thread-safe wrapper. But understanding the heap property helps you choose the right tool and debug performance issues. When done badly — for example, using a full sort every time you need the next best item — the system grinds to a halt as data grows. The heap is the quiet workhorse behind countless AI systems, and now you know how it works.


---

Read this on the web: https://basavapurushottam.com/learn-ai/heaps-and-priority-queues
