A heap is a tree-based data structure in which every parent node obeys a fixed ordering rule with respect to its children. In a max-heap every parent is greater than or equal to both its children; in a min-heap every parent is less than or equal to both. Heaps are the most efficient implementation of a priority queue.
What is the difference between a max-heap and a min-heap?
Picture a school sports day leaderboard. In a max-heap, the student with the highest score is always at the top — the root. Every student above another in the tree has an equal or higher score. In a min-heap, the student with the lowest score (perhaps the fastest sprint time) stays at the root.
| Property | Max-heap | Min-heap |
|---|---|---|
| Root holds | Maximum value | Minimum value |
| Parent vs child | Parent ≥ both children | Parent ≤ both children |
| Common use | Access largest element quickly | Access smallest element quickly |
| Example application | Task scheduler (highest priority first) | Dijkstra's algorithm (shortest path first) |
The heap ordering rule is called the heap property. Crucially, a heap does NOT guarantee full sorting — siblings at the same level can be in any order. Only the parent-child relationship is guaranteed.
How is a heap stored in an array?
Heaps are usually stored as arrays, not as explicit tree nodes with pointers. For a node at index i (using 0-based indexing):
Left child → index 2i + 1
Right child → index 2i + 2
Parent → index (i - 1) // 2
For example, the max-heap [90, 75, 80, 45, 60, 50, 30]:
Array index: 0 1 2 3 4 5 6
Value: 90 75 80 45 60 50 30
Tree view:
90 (i=0)
/ \
75 (i=1) 80 (i=2)
/ \ / \
45 60 50 30
(i=3) (i=4) (i=5) (i=6)
This array representation eliminates the memory overhead of storing left/right pointers, making heaps extremely memory-efficient.
What is heapify?
Heapify is the operation that restores the heap property after an element has been added or removed.
Sift-up (used when inserting): Place the new element at the end of the array. If it violates the heap property with its parent, swap them. Repeat, moving up the tree, until the property is restored or the root is reached.
Sift-down (used when removing): When the root is removed (the typical operation — it holds the maximum or minimum), replace it with the last element. Then swap it down with its larger (max-heap) or smaller (min-heap) child until the heap property is restored.
Both operations are O(log n) because the tree height grows logarithmically with the number of elements.
How does a heap implement a priority queue?
A priority queue is an abstract data type in which each element has an associated priority, and the element with the highest priority is always removed first. A max-heap implements this directly:
push(item, priority): insert item with its priority — O(log n)
pop(): remove and return the item at the root — O(log n)
peek(): return the root's item without removing it — O(1)
Compare this with a simpler list-based priority queue, where pop() would require scanning the whole list at O(n). The heap is significantly faster for large datasets.
| Operation | Sorted list | Unsorted list | Heap |
|---|---|---|---|
| Insert | O(n) | O(1) | O(log n) |
| Remove max/min | O(1) | O(n) | O(log n) |
| Peek max/min | O(1) | O(n) | O(1) |
What is heap sort?
Heap sort uses a max-heap to sort an array in ascending order:
- Build a max-heap from the unsorted array — O(n).
- The root holds the maximum element. Swap it with the last element of the heap portion.
- Shrink the heap by one and sift the new root down — O(log n).
- Repeat steps 2–3 until the heap is empty.
Heap sort has a worst-case time complexity of O(n log n) — the same as merge sort — and a space complexity of O(1) because it sorts in place. However, it is less cache-friendly than merge sort in practice.
Where are heaps used in real computing systems?
- Operating system schedulers — the OS process scheduler often uses a min-heap keyed by priority level and next-scheduled time. The process with the earliest wakeup time is always at the root.
- Dijkstra's algorithm — a min-heap stores unvisited nodes keyed by their current shortest distance, making each "extract the nearest unvisited node" step O(log n).
- Event-driven simulation — events are stored in a min-heap keyed by the time they occur, so the next event to process is always at the root.
- Streaming top-k queries — to find the ten most popular search queries from a billion-row log, a min-heap of size 10 processes the stream efficiently.
Frequently asked questions
What is a heap in simple terms for GCSE?
A heap is a nearly complete binary tree stored as an array, in which every parent is always larger than both its children (max-heap) or smaller (min-heap). The root always holds the maximum or minimum value, so you can access it in O(1) time. Heaps are the standard way to implement a priority queue efficiently.
What is the time complexity of heap operations?
Inserting an element into a heap takes O(log n) time because the new element may need to sift up through at most log n levels. Removing the root takes O(log n) because the replacement element may need to sift down through the same height. Looking at the root (peek) without removing it takes O(1) time.
How is a heap different from a binary search tree?
A binary search tree (BST) maintains a full ordering: every node is greater than all nodes in its left subtree and less than all nodes in its right subtree. A heap only guarantees the parent-child relationship, not the sibling relationship. As a result, searching a heap for an arbitrary element is O(n) (you must check everything), while a balanced BST supports O(log n) search.
Do I need to know heap sort for GCSE Computer Science?
Some specifications (particularly at the more demanding end of GCSE and at A-level) include heap sort. At GCSE, you are more likely to be examined on what a heap is, how the heap property works, and why heaps implement priority queues efficiently. Check your specific exam-board specification — AQA and OCR syllabuses differ in the depth of coverage they require.
Work through heap diagrams and priority-queue problems with Professor Turing at aitutors.me — hints are waiting, not answers.