Data Structures & Big-O (CS 201) · Module 5 of 9
Heaps & Priority Queues
The array-backed tree structure that keeps the most important element always one step away.
The Heap Property
- A binary heap is a complete binary tree satisfying the heap property: in a min-heap, every parent is less than or equal to its children — in a max-heap, parent ≥ children.
- Because it's a complete tree, a heap can be efficiently stored in an array, with a node at index i having children at indices 2i+1 and 2i+2.
In a min-heap, what can you say about the relationship between the root and every other node in the heap?
Solution. The root is always less than or equal to every other node in the heap, since the heap property (parent ≤ children) applied recursively means the minimum value is always at the root.
Insertion & Extraction
- Inserting into a heap adds the element at the next open spot and "bubbles it up," swapping with its parent, until the heap property is restored, taking O(log n) time.
- Extracting the min (or max) removes the root, moves the last element to the root, and "bubbles it down," swapping with the smaller/larger child, until the heap property is restored — also O(log n).
Why does inserting into or extracting from a heap take O(log n) time?
Solution. Both operations only need to move an element up or down along a single path from a leaf to the root (or vice versa), and since the heap is a complete binary tree, its height is O(log n), bounding the number of swaps needed.
Heapify & Heap Sort
- Building a heap from an unsorted array ("heapify") can be done in O(n) time, not O(n log n), using a bottom-up approach, since most nodes are near the bottom and require little work to fix.
- Heap sort repeatedly extracts the maximum from a max-heap and places it at the end of the array, achieving O(n log n) time in-place, though it is not a stable sort.
Why is heap sort considered an in-place sorting algorithm?
Solution. It sorts the array by repeatedly swapping the root (max element) to the end and shrinking the heap, doing all its work within the original array without needing significant additional memory.
Priority Queue Applications
- A priority queue, commonly implemented with a heap, always returns the highest (or lowest) priority element first, regardless of insertion order.
- Priority queues are essential in algorithms like Dijkstra's shortest path and in task scheduling systems where certain tasks need to be processed before others.
Why is a heap a natural choice for implementing a priority queue?
Solution. A heap always keeps the highest (or lowest) priority element at the root, accessible in O(1) time, and supports O(log n) insertion and removal, efficiently maintaining priority order as elements are added and removed.
Check yourself
2 of this module's 5 quiz questions. Pick your answers, then check them in the app, with an explanation for every question.
1. What is the heap property for a min-heap?
2. What is the time complexity of inserting into a heap?