Understanding Heaps: Min-Heaps, Max-Heaps, and Priority Queues

Imagine a job queue where new tasks keep arriving, but the next task must be chosen by priority rather than arrival time. Sorting the entire queue after every insertion would work, but it does more work than necessary if you only care about the most urgent task. A heap addresses this problem by keeping the highest-priority element easy to access without keeping every element in sorted order.

In this article, we will build an understanding of binary heaps from the ground up. We will connect the tree structure to its array representation, walk through insertion and root removal, and explain how to build a heap from an existing array. Two interactive labs let you explore the transitions, and runnable Java examples let you check the results.

1. Is a heap data structure the same as heap memory?

No. Programming languages also use the word heap for a memory region where dynamically allocated objects may live. This article discusses a data structure with a particular ordering rule, rather than a memory-management mechanism. A binary heap can be represented by an ordinary array. Sharing a name does not make these two concepts the same mechanism.

2. What problem does a heap solve?

Consider a system that repeatedly performs two operations: insert a new element, and select and remove the current smallest or largest element. In an unsorted array, insertion is inexpensive, but each selection requires a scan of the array. In a sorted array, finding an extreme element is easy, but inserting a new value in the correct position may require shifting many elements.

A heap offers a useful balance between these operations. Reading the root takes constant time, while maintaining the tree order after insertion or root removal requires a logarithmic number of steps. This makes heaps a common implementation of a priority queue. A priority queue describes the behavior an interface provides; a binary heap is one data structure that can provide that behavior.

3. The two rules of a binary heap

The shape rule: a complete binary tree

A binary heap is a complete binary tree: every level except possibly the last is full, and the last level fills from left to right without gaps. Every node does not need to have two children, and the final level does not need to be full. This shape keeps the tree height at O(log n) and allows us to store its nodes consecutively in an array.

The ordering rule: the relationship between parents and children

In a min-heap, every parent is less than or equal to each of its children, so the smallest element is at the root. A max-heap reverses this relationship: every parent is greater than or equal to each child, so the largest element is at the root. Duplicate values are valid in both structures.

Min-heap                 Max-heap       2                        20     /   \                     /  \    5     8                  14    18   / \   /                  / \   /  9  12 10                 7  10  3

This rule does not mean the entire array is sorted. In the min-heap above, 8 may appear after 9 in the array representation. Siblings have no additional ordering requirement. A heap constrains each node relative to its descendants through parent-child relationships. Together, these local relationships guarantee that the root is the global minimum or maximum.

4. How does the tree fit inside an array?

Reading the tree level by level, from left to right, gives its array representation. The example min-heap becomes [2, 5, 8, 9, 12, 10]. We do not need separate node objects or pointer fields to locate children; their indices are enough.

Zero-based indexing (Java integer division):parent(i) = (i - 1) / 2    // only for i > 0left(i)   = 2 * i + 1right(i)  = 2 * i + 2Index:   0  1  2  3   4   5Value:  [2, 5, 8, 9, 12, 10]

For example, the children of 5 at index 1 are at indices 3 and 4, holding 9 and 12. The left child of 8 at index 2 is at index 5, holding 10. Its calculated right-child index is 6, which is outside the array, so that child does not exist. Only calculate a parent when i > 0: Java integer division makes (0 - 1) / 2 equal to 0, which would incorrectly treat the root as its own parent.

5. Insertion: why append first and move upward?

To insert into a min-heap, first append the new element to the array. This preserves the shape rule and leaves no gaps in the tree. Compare the element with its parent. If the new element is smaller, swap them and move up one level. Stop when the parent is smaller than or equal to the element, or when the element reaches the root. This operation is called sift-up, bubble-up, or swim.

Insert 1 into [2, 5, 8, 9, 12, 10]. Appending gives [2, 5, 8, 9, 12, 10, 1]. The parent of 1 is 8 at index 2. After their swap, the array is [2, 5, 1, 9, 12, 10, 8]. Now compare 1 with the root, 2. A second swap gives [1, 5, 2, 9, 12, 10, 8]. The inserted element has reached the root, so the operation is complete.

There is no need to inspect the entire tree. Starting from a valid heap, only the path from the inserted node to the root can need repair. Each iteration moves up one level, so the number of iterations is bounded by the tree height.

6. Removing the minimum: what replaces the root?

After removing the minimum at the root, we cannot leave the root empty. Move the final array element into the root and remove the final array slot. This preserves the shape rule, but the replacement root may be larger than its children. Repair the order by moving downward, using sift-down or sink.

When a min-heap node has two children, choose the smaller child. If the parent is larger than that child, swap them and continue downward. Stop when the parent is no larger than either child, or when it has no children. Choosing the larger child can leave the relationship with the smaller child broken. In a max-heap, choose the larger child instead.

Remove 2 from [2, 5, 8, 9, 12, 10]. Moving the final element, 10, to the root gives [10, 5, 8, 9, 12]. Compare 10 with children 5 and 8, and choose 5. Swapping gives [5, 10, 8, 9, 12]. The children of 10 are now 9 and 12. Swap with 9 to obtain [5, 9, 8, 10, 12]. The value 10 is now a leaf, so the repair is complete.

7. Peek, pop, and key updates are different operations

Peek reads the root without changing the data structure. Pop, also called extract-min for a min-heap, removes the root and restores heap order. An API should define what happens on an empty heap. Our custom Java implementation throws NoSuchElementException for both peek and pop. Java's standard PriorityQueue instead returns null from peek and poll when empty; element and remove throw NoSuchElementException.

To change a particular element's priority, you first need to locate it. If its index is known, updating its key and moving it upward or downward takes O(log n). If only its value is known, finding it in an ordinary binary heap can take O(n). Systems with frequent updates can maintain a map from element identity to heap index. Every swap must update that map as well.

8. Build-heap: turning an existing array into a heap

If all n elements are available at the start, you do not need to insert them into an empty heap one at a time. Bottom-up build-heap applies sift-down to each internal node, starting with the final parent and moving toward the root. In a zero-indexed array, the final parent is at n / 2 - 1, using Java integer division. All later nodes are leaves, and a single-node subtree already satisfies heap order.

Start with [9, 4, 7, 1, 3, 6]. At i = 2, swap 7 with 6 to get [9, 4, 6, 1, 3, 7]. At i = 1, swap 4 with 1 to get [9, 1, 6, 4, 3, 7]. Finally, sift the root value 9 down by swapping first with 1 and then with 3. The result is [1, 3, 6, 4, 9, 7]. This is a min-heap, but it is not a sorted array.

Why is build-heap O(n) rather than O(n log n)?

Assigning a worst-case O(log n) cost to every node gives a valid but loose upper bound. Most nodes are near the bottom and cannot move very far. Roughly half are leaves and need no downward movement. Roughly a quarter can move at most one level, and an eighth can move at most two levels. The number of nodes that can travel a long distance decreases rapidly.

Total work, ignoring constant factors:(n / 4) * 1 + (n / 8) * 2 + (n / 16) * 3 + ... = O(n)This bound applies to bottom-up build-heap.Inserting n elements into an empty heap has an O(n log n) upper bound.

9. Operation costs

Operation                     Binary heap costRead the root (peek)          O(1)Sift upward                  O(log n) worst caseRemove root and repair       O(log n) structural costBottom-up build-heap         O(n)Find an arbitrary value      O(n) worst caseUpdate a key at a known index O(log n)Store all elements           O(n) space

These bounds assume comparisons and swaps have constant cost. Resizing the underlying array can make an individual insertion cost O(n). When dynamic-array resizing is amortized, push has an O(log n) amortized bound. Keep the logarithmic cost of repairing heap order separate from the memory-management cost of the underlying array.

10. Implementing a min-heap in Java

The following Java 17-compatible class stores integer values in an ArrayList. Its constructor copies the input values, leaving the original array unchanged. Sift-up and sift-down use loops, so they do not need a recursion stack. Bottom-up construction takes O(n) time, and the copied elements occupy O(n) space. Save each Java example in the file named above its code block, then compile with javac and run its public class with java.

import java.util.ArrayList;import java.util.List;import java.util.NoSuchElementException;public final class MinHeap {    private final ArrayList<Integer> data;    public MinHeap(int... values) {        data = new ArrayList<>(values.length);        for (int value : values) {            data.add(value);        }        for (int i = data.size() / 2 - 1; i >= 0; i--) {            siftDown(i);        }    }    public int size() {        return data.size();    }    public int peek() {        if (data.isEmpty()) {            throw new NoSuchElementException("peek from empty heap");        }        return data.get(0);    }    public void push(int value) {        data.add(value);        int i = data.size() - 1;        while (i > 0) {            int parent = (i - 1) / 2;            if (data.get(parent) <= data.get(i)) {                break;            }            swap(parent, i);            i = parent;        }    }    public int pop() {        if (data.isEmpty()) {            throw new NoSuchElementException("pop from empty heap");        }        int smallest = data.get(0);        int last = data.remove(data.size() - 1);        if (!data.isEmpty()) {            data.set(0, last);            siftDown(0);        }        return smallest;    }    private void siftDown(int i) {        int size = data.size();        // Nodes at indices >= size / 2 are leaves.        while (i < size / 2) {            int left = 2 * i + 1;            int right = left + 1;            int smallest = left;            if (right < size && data.get(right) < data.get(left)) {                smallest = right;            }            if (data.get(i) <= data.get(smallest)) {                return;            }            swap(i, smallest);            i = smallest;        }    }    private void swap(int a, int b) {        int value = data.get(a);        data.set(a, data.get(b));        data.set(b, value);    }    public static void main(String[] args) {        MinHeap heap = new MinHeap(2, 5, 8, 9, 12, 10);        heap.push(1);        System.out.println(heap.peek()); // 1        List<Integer> sorted = new ArrayList<>();        while (heap.size() > 0) {            sorted.add(heap.pop());        }        System.out.println(sorted); // [1, 2, 5, 8, 9, 10, 12]    }}

The conditional inside pop matters. When the heap contains one element, removing the final element leaves the array empty, so there is no index 0 to overwrite. Sift-down also checks that a right child exists before accessing it. Parents with only a left child are normal near the final level.

11. Using the standard library in application code

Implementing a heap helps explain the mechanism; in application code, Java's PriorityQueue is often the better choice. Natural integer ordering gives a min-priority queue, while Comparator.reverseOrder() selects the largest value first. Constructing a queue from a List copies its elements without changing that list. Use offer to insert, peek to read the head, and poll to remove it. Iterating over or printing a PriorityQueue does not guarantee sorted order; repeatedly poll it when you need ordered output. The queue does not accept null elements.

import java.util.Comparator;import java.util.List;import java.util.PriorityQueue;public class HeapLibraryExample {    public static void main(String[] args) {        List<Integer> numbers = List.of(9, 4, 7, 1, 3, 6);        PriorityQueue<Integer> minHeap = new PriorityQueue<>(numbers);        minHeap.offer(2);        System.out.println(minHeap.peek()); // 1: read only        System.out.println(minHeap.poll()); // 1: remove the minimum        System.out.println(minHeap.poll()); // 2        System.out.println(numbers); // [9, 4, 7, 1, 3, 6]: unchanged        PriorityQueue<Integer> maxHeap =                new PriorityQueue<>(Comparator.reverseOrder());        maxHeap.addAll(numbers);        System.out.println(maxHeap.peek()); // 9    }}

12. Priority queues and equal priorities

A heap does not automatically provide FIFO ordering. If equally important tasks must be returned in arrival order, represent that policy explicitly. The Java example uses a Task record containing priority, sequence, and name, with a comparator that orders by priority and then sequence. Smaller priority numbers mean more urgent tasks. An increasing sequence number breaks ties by arrival order. Comparator.comparingInt and thenComparingLong avoid the integer overflow that can occur with subtraction-based comparators. The immutable record also prevents priorities from being changed accidentally while queued.

import java.util.Comparator;import java.util.PriorityQueue;public class TaskQueueExample {    private record Task(int priority, long sequence, String name) {}    public static void main(String[] args) {        PriorityQueue<Task> queue = new PriorityQueue<>(                Comparator.comparingInt(Task::priority)                        .thenComparingLong(Task::sequence));        long sequence = 0;        queue.offer(new Task(2, sequence++, "report"));        queue.offer(new Task(1, sequence++, "alarm"));        queue.offer(new Task(1, sequence++, "notification"));        while (!queue.isEmpty()) {            System.out.println(queue.poll().name());        }        // alarm        // notification        // report    }}

13. Keeping the largest k elements from a stream

Suppose millions of numbers arrive, but you only need to keep the largest ten. You do not need to retain and sort the entire stream. Maintain a min-heap of size k. Its root is the smallest among the current largest-k candidates: the threshold a new candidate must beat to enter the selected group.

Insert values until the heap reaches size k. After that, replace the root only when the next value is larger than it; otherwise, leave the selected group unchanged. A min-heap is useful here because we need quick access to the weakest candidate among the large values we are keeping.

import java.util.ArrayList;import java.util.Comparator;import java.util.List;import java.util.PriorityQueue;public class TopKExample {    public static List<Integer> largestK(Iterable<Integer> stream, int k) {        if (k < 1) {            return List.of();        }        PriorityQueue<Integer> selected = new PriorityQueue<>();        for (int value : stream) {            if (selected.size() < k) {                selected.offer(value);            } else if (value > selected.peek()) {                selected.poll();                selected.offer(value);            }        }        List<Integer> result = new ArrayList<>(selected);        result.sort(Comparator.reverseOrder());        return result;    }    public static void main(String[] args) {        System.out.println(largestK(List.of(8, 1, 12, 4, 19, 3, 10), 3));        // [19, 12, 10]    }}

For k >= 2 and k <= n, processing the stream takes O(n log k) time and storing the candidates takes O(k) space. Sorting the final output adds O(k log k) time. For the special case k = 1, a single running maximum processes the stream in O(n) time. If all the input is already in memory and k is close to n, sorting the whole collection may be simpler and more practical.

14. How heapsort works

Classic in-place heapsort first builds a max-heap in the array. The largest element is at the root. Swap it with the final element in the active range, then reduce the active heap size by one. That final position is now settled. Sift the replacement root down within the remaining range, and repeat. When the process finishes, the array is sorted in ascending order.

Building the heap takes O(n), and the extraction phase takes O(n log n) in total. The classic in-place version can use O(1) extra space with iterative sift-down. Building a separate min-heap and popping every element into a new result list also produces sorted output, but uses O(n) extra space. These approaches have different memory properties. Standard heapsort is not stable: records with equal keys may lose their original relative order.

15. How a heap differs from a binary search tree

A binary search tree partitions the left and right subtrees by key ranges. A heap provides no such guarantee; it maintains parent-child priority relationships. A balanced BST can therefore support searches and range queries efficiently, while a heap is useful for repeatedly selecting an extreme priority. Assuming that an arbitrary value can be found in a heap in logarithmic time is a common mistake.

16. Where heaps help, and where they do not

• Task and event scheduling: select the event with the earliest timestamp or highest priority. Real systems also need explicit policies for retries, cancellation, and equal priorities.
• Merging sorted streams: keep the next candidate from each stream in a heap and select the smallest. With k streams, each selection and heap repair takes O(log k) time for k >= 2.
• Graph algorithms: a priority queue can help select the next candidate in algorithms such as Dijkstra's. Remember that Dijkstra's algorithm is not generally correct when edges can have negative weights.
• Streaming statistics: retain the top k candidates, or track a running median using two heaps. A two-heap median also requires maintaining the heap sizes and the ordering relationship between the two groups.

If you only need to find a minimum once, a linear scan takes O(n), and building a heap may add unnecessary complexity. If your main operations are sorted traversal, range queries, or locating records by key, a different structure may be more suitable. Choose based on the operations your workload performs most often.

17. Common mistakes

• Treating the heap array as sorted. The root is the correct extreme element; the other positions are not guaranteed to be in sorted order.
• Choosing the larger child during min-heap sift-down, or checking only the left child when a right child exists.
• Calculating a parent for the root, forgetting a right-child bounds check, or mishandling pop on a single-element heap.
• Changing a comparison key in place without repairing the heap. A key update can invalidate the ordering guarantee.
• Assuming equal priorities imply FIFO behavior. Add an explicit tie-breaker, such as an arrival sequence number, when required.
• Confusing bottom-up heapify with repeated insertion. The linear O(n) construction bound applies to bottom-up build-heap.

18. Check your understanding

Try these questions on paper before checking with the algorithm: Is [3, 6, 5, 9, 8, 7] a min-heap? Which indices change when 2 is inserted? If 3 is removed from the original heap, which child is selected first? Finally, explain why an ascending sorted array can also be a min-heap, but a min-heap does not have to be sorted.

Answers: The original array is a valid min-heap. Inserting 2 follows indices 6 -> 2 -> 0 and produces [2, 6, 3, 9, 8, 7, 5]. Removing 3 from the original heap moves the final value 7 to the root. The smaller child, 5, is selected, producing [5, 6, 7, 9, 8]. Both results satisfy heap order without sorting the entire array.

The central idea of a heap is to keep the extreme element accessible while doing only enough work to maintain that guarantee. Array index relationships preserve the shape, and sift-up and sift-down repair the affected path. Together, these ideas connect priority queues, top-k selection, and heapsort as different uses of the same underlying mechanism.

References and further reading

Princeton Algorithms: Priority Queues — binary heaps and analysis

MIT 6.006: Binary Heaps — lecture notes

Java PriorityQueue — Java SE 17 API reference