--- title: Heaps source: 'https://academia.sh/en/courses/data-structures/heaps' course: 'Data Structures' language: en updated: '2026-08-17T18:08:02+00:00' license: 'CC BY-SA 4.0' --- # Heaps Priority queues, the heap condition, array representation, sift-up and sift-down, and the linear cost of building a heap. The queues lesson left a question open: what happens when the order elements arrived in does not matter, but their **priority** does? An operating system decides which process to run, and a routing algorithm decides which node to expand, by looking at priority. A **priority queue** is the abstract data type that answers this question: elements are inserted, and the one removed is always the **highest-priority** one. ## Full Ordering Is Not Required A priority queue can be implemented with a sorted structure — each insertion is placed in order, and the front is removed. But this does more work than necessary: the queue only needs to know the **next** element; the exact order of the rest does not matter. A **heap** strikes a balance between full ordering and no ordering at all. Its condition is: > Every node's value is less than or equal to the values of its children (a min-heap). This is a **partial** ordering. There is no relationship between siblings; order is maintained only along the parent–child axis. That the root is the smallest element follows directly from this condition. A max-heap is the reverse condition and holds the largest element at the root. ## Complete Tree and Array Representation A heap is always a **complete binary tree**: levels fill from left to right, and any gap appears only at the right end of the last level. This shape guarantee makes the array representation from the binary trees lesson directly applicable: $$ \text{left}(i) = 2i+1, \qquad \text{right}(i) = 2i+2, \qquad \text{parent}(i) = \left\lfloor \tfrac{i-1}{2} \right\rfloor $$ The heap holding no pointers has two consequences: there is no memory overhead, and cache behavior is good because elements sit contiguously. The tree structure is only conceptual; the underlying data is a plain array. ## Two Sift Operations The heap condition is restored through two local repair operations. **Sift-up** is used on insertion. The new element is placed at the end of the array — the tree's last leaf — and swapped upward with its parent until the condition holds. **Sift-down** is used on removal. When the root is removed, the last element takes its place and is swapped downward with its smaller child until the condition holds. Both operations move along a path from the root to a leaf; their cost is $O(\log n)$. ```python class Heap: """Min-heap: the root is always the smallest element.""" def __init__(self) -> None: self._data: list[int] = [] def __len__(self) -> int: return len(self._data) def insert(self, value: int) -> None: self._data.append(value) self._sift_up(len(self._data) - 1) def smallest(self) -> int: if not self._data: raise IndexError("heap is empty") return self._data[0] def remove(self) -> int: if not self._data: raise IndexError("heap is empty") smallest = self._data[0] last = self._data.pop() if self._data: self._data[0] = last # last element is moved to the root self._sift_down(0) return smallest def _sift_up(self, i: int) -> None: while i > 0: parent = (i - 1) // 2 if self._data[i] >= self._data[parent]: break # condition holds self._data[i], self._data[parent] = self._data[parent], self._data[i] i = parent def _sift_down(self, i: int) -> None: n = len(self._data) while True: smallest, left, right = i, 2 * i + 1, 2 * i + 2 if left < n and self._data[left] < self._data[smallest]: smallest = left if right < n and self._data[right] < self._data[smallest]: smallest = right if smallest == i: break self._data[i], self._data[smallest] = self._data[smallest], self._data[i] i = smallest h = Heap() for measurement in (25, 7, 30, 12, 18, 3): h.insert(measurement) print(h.smallest(), len(h)) # 3 6 print([h.remove() for _ in range(6)]) # [3, 7, 12, 18, 25, 30] ``` Elements coming out in sorted order during removal does not mean the heap itself is sorted: the array is never fully sorted at any point. The sorted output arises from each removal selecting the smallest. ## The Cost of Building a Heap If an array already exists and the whole thing needs to become a heap, inserting each element one at a time takes $O(n \log n)$. A better way exists: apply sift-down going backward, starting from the **last internal node** in the array. ```python def build_heap(data: list[int]) -> Heap: """Turns an existing array into a heap in place: O(n).""" h = Heap() h._data = list(data) for i in range(len(data) // 2 - 1, -1, -1): # from the last internal node to the root h._sift_down(i) return h h = build_heap([25, 7, 30, 12, 18, 3]) print(h.smallest()) # 3 print([h.remove() for _ in range(6)]) # [3, 7, 12, 18, 25, 30] ``` Contrary to intuition, this method's cost is not $O(n \log n)$ but $O(n)$. The reason lies in the distribution of nodes: half the nodes are leaves and are never sifted; a quarter sift one level, an eighth sift two levels. The total ends up markedly smaller than the assumption that every node pays the maximum cost would suggest. The precise analysis belongs to the **Algorithms** course. ## Uses **Priority scheduling.** Operating system process selection, choosing the next event in event-driven simulations. **Graph algorithms.** Shortest-path and minimum-spanning-tree algorithms pull the cheapest edge in line from the heap. These algorithms are covered in the **Algorithms** course. **Top-k elements.** Finding the largest hundred values among millions does not require sorting all of them: a heap of a hundred elements is kept, and each new value is compared against the root. Memory is $O(k)$ and the cost is $O(n \log k)$. **Streaming median.** A two-heap pattern introduced in the Programming Fundamentals course: keeping the smaller half in a max-heap and the larger half in a min-heap gives the median in constant time. **Sorting.** Placing every element into a heap and removing them one at a time is an $O(n \log n)$ sorting algorithm known as heapsort. One detail becomes important in algorithms that use a priority queue: if the priority of an element already in the heap changes later, the structure does not correct itself. Either a priority-update operation is implemented separately, or the old entry is treated as invalid and a new one is inserted; the second approach is simpler and lets invalid entries accumulate in the heap. ## Cost Table | Operation | Heap | Sorted array | Unsorted array | |---|---|---|---| | View smallest | $O(1)$ | $O(1)$ | $O(n)$ | | Insertion | $O(\log n)$ | $O(n)$ | $O(1)$ | | Remove smallest | $O(\log n)$ | $O(1)$* | $O(n)$ | | Build heap | $O(n)$ | $O(n \log n)$ | $O(1)$ | | Search (random element) | $O(n)$ | $O(\log n)$ | $O(n)$ | \* $O(n)$ if removal from the front requires shifting. The last row is the heap's limitation: finding any element other than the root requires traversing the entire structure. A heap is designed for **access to the extreme element**, not for sorting. ## Summary - A priority queue is the abstract type that returns the highest-priority element on removal. - The heap condition is a partial ordering: a parent is smaller than its children, and there is no relationship between siblings. - A heap is always a complete binary tree and is represented as an array; there is no pointer overhead. - Insertion repairs the condition with sift-up, removal with sift-down; both are logarithmic. - Building a heap from an existing array is cheaper than inserting one at a time and runs in linear time. - A heap is designed for access to the extreme element; searching for a random element is linear. ## Next Step The search structures covered so far compared keys as whole units. When keys are strings, a different possibility arises: shared prefixes can be stored once, and comparison can proceed character by character. The next lesson covers the trie, which is built on this idea.