This post assumes arrays, trees, and basic Java. Review Data Structures and Big O Notation for those foundations.
What are Heaps?
A heap is a tree-based data structure that keeps an extreme value at its root. In a min-heap, each parent is less than or equal to its children, so the root holds a minimum. In a max-heap, each parent is greater than or equal to its children, so the root holds a maximum. This parent-child relationship is called the heap-order property.
The purpose is to answer “which item comes first by priority?” efficiently as values arrive and leave. For example, a scheduler can use a min-heap of event times to select the earliest event. It does not need every event to be fully sorted; it needs the next event at the root.
A priority queue specifies that access pattern: insert an item, inspect the next item by priority, and remove it. A heap is a way to implement it. This differs from a FIFO queue, which selects by arrival order, and from a sorted sequence, which maintains the order of all items.
There are several heap designs. Here we will develop the binary heap, a common implementation that combines heap order with a compact tree shape. After explaining its characteristics and operations, we will use Java’s implementation to retain the largest values in a stream. The data structure discussed here is separate from the memory region also called the heap.
What are Heaps characteristics?
Heap Order and Binary Heap Shape
A binary heap combines the heap-order property with a shape rule. Both rules matter: ordering exposes the next priority, while shape keeps the paths used during updates short.
The shape is a complete binary tree: all levels are full except possibly the last, which fills from left to right. This keeps the height logarithmic and lets us store the tree compactly in an array without explicit child pointers.
Repeating the min-heap ordering relationship down each path ensures that no descendant is smaller than the root. A max-heap reverses the comparisons. Neither form requires distinct values; equal values are allowed.
Consider this min-heap:
flowchart TB
A["2: index 0"] -->|"Left child"| B["5: index 1"]
A -->|"Right child"| C["3: index 2"]
B -->|"Left child"| D["9: index 3"]
B -->|"Right child"| E["7: index 4"]
C -->|"Left child"| F["8: index 5"]
Each parent satisfies the rule: 2 ≤ 5, 2 ≤ 3, 5 ≤ 9, 5 ≤ 7, and 3 ≤ 8. Yet the left child 5 exceeds the right child 3. That is valid: the rule orders ancestors and descendants, not siblings or entire subtrees relative to each other.
A heap therefore differs from a binary search tree. You cannot use a left-versus-right comparison to locate an arbitrary value. Nor is its array representation sorted.
Array Representation
Store the nodes level by level, from left to right:
1
2
Index: 0 1 2 3 4 5
Value: 2 5 3 9 7 8
For a zero-based index i, the navigation rules are:
| Relationship | Index calculation |
|---|---|
| Left child | 2 * i + 1 |
| Right child | 2 * i + 2 |
Parent, when i > 0 | (i - 1) / 2, using integer division |
For index 1, the children are indices 3 and 4, containing 9 and 7. Its parent is index 0, containing 2. A calculated child index at or beyond the heap’s size means that child is absent.
Because the tree is complete, insertion adds at the next array position, and removal can take the last position. Both operations preserve the shape. The remaining work is to repair the ordering along a single path.
Insertion by Sifting Up
Insert 1 into our example. Append it at index 6 first:
| Step | Array | Reason |
|---|---|---|
| Append | [2, 5, 3, 9, 7, 8, 1] | Index 6 is the next free position |
| Swap with parent | [2, 5, 1, 9, 7, 8, 3] | 1 < 3, so the parent relationship is broken |
| Swap with root | [1, 5, 2, 9, 7, 8, 3] | 1 < 2, so move it up again |
We stop at the root. This process is called sifting up. Only the new element’s ancestor path can have become invalid; all other parent-child relationships remain untouched. At most, the inserted value travels the height of the tree.
Removal by Sifting Down
Now remove the minimum 1. Leaving the root empty would break the shape, so move the last value, 3, to the root and shrink the array:
1
[3, 5, 2, 9, 7, 8]
The root’s children are 5 and 2. We swap with the smaller child, producing:
1
[2, 5, 3, 9, 7, 8]
The moved 3 now has child 8, so the ordering is valid and we stop. This is sifting down.
Choosing the smaller child matters. Swapping with 5 instead would leave 5 above 2, so the root would still violate the min-heap rule. At each step we fix the current parent and continue only into the subtree containing the displaced value.
Construction from Existing Values
You can build a heap by inserting each value, costing O(n log n) in the worst case. Bottom-up heap construction does better: treat the input array as a complete tree, then sift down each internal node from index n / 2 - 1 back to 0.
Leaves already satisfy the rule. Processing parents after their children means each sift operates on subtrees that are already heaps. Most nodes are near the bottom and can move only a little: roughly half are leaves, a quarter can move one level, and an eighth can move two. The total work follows n/4 + 2n/8 + 3n/16 + ..., which is O(n). MIT’s binary heap lecture notes develop this construction and its analysis.
Heap construction does not sort the array. Extracting all values afterward still requires repeated removals, giving O(n log n) total time.
Time and Space Costs
For a binary heap of size n, with constant-cost comparisons:
| Operation | Cost | Why |
|---|---|---|
| Inspect root | O(1) | Root has a known position |
| Sift after insertion | O(log n) worst case | Follow one ancestor path |
| Remove root | O(log n) worst case | Follow one descendant path |
| Find an arbitrary value | O(n) worst case | No left-versus-right search rule |
| Bottom-up construction | O(n) | Most nodes move only a few levels |
Array growth is separate from sifting. A single insertion into a full backing array may require O(n) copying, even though its ordering repair is O(log n). With geometric array growth, the copying cost is amortized over many insertions; it does not make every insertion constant-latency. Java’s API documents logarithmic enqueue/dequeue and linear arbitrary-value search/removal, while leaving the capacity growth policy unspecified. See the implementation note.
The array stores one entry per value, so a binary heap uses O(n) storage. The compact representation avoids explicit child pointers, although a resizable array may keep spare capacity.
Heaps in action - code examples
Using a Priority Queue in Java
For integers, Java’s PriorityQueue exposes the smallest value first by default. offer inserts, peek inspects the head, and poll removes it; the last two return null when empty. Iteration does not produce sorted order. Equal-priority items have no FIFO guarantee. These behaviors are specified in the PriorityQueue API.
To expose the largest integer first, provide Comparator.reverseOrder() when constructing the queue. A comparator defines which item comes before another; for object priorities, use comparison methods rather than subtraction, which can overflow. Avoid changing an item’s priority while it remains inside the queue: remove and reinsert it so the structure can restore its ordering.
Keep the Largest Three Values
Suppose values arrive as 12, 4, 19, 7, 25, 18. We could sort them all, but we only need the three largest. Keep a min-heap of at most three retained values. Its root is the smallest retained candidate, making it the threshold a new value must beat.
Once the heap is full, discard values at or below the root. For a larger value, remove the root and insert the replacement. This maintains the invariant: after each input, the heap contains the largest three values seen so far, or all values if fewer than three have arrived.
Save the complete example as TopValues.java:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class TopValues {
public static List<Integer> largest(int[] values, int k) {
if (k < 1) {
throw new IllegalArgumentException("k must be positive");
}
PriorityQueue<Integer> retained = new PriorityQueue<>();
for (int value : values) {
if (retained.size() < k) {
retained.offer(value);
} else if (value > retained.peek()) {
// Remove the weakest retained candidate before adding a better one.
retained.poll();
retained.offer(value);
}
}
// Polling produces ascending order; iterating the heap would not.
List<Integer> result = new ArrayList<>();
while (!retained.isEmpty()) {
result.add(retained.poll());
}
return result;
}
public static void main(String[] args) {
int[] values = {12, 4, 19, 7, 25, 18};
System.out.println(largest(values, 3));
}
}
Run javac TopValues.java and then java TopValues:
1
[18, 19, 25]
Here is the decision after each arrival. The middle column shows retained values in sorted order for readability, rather than claiming an internal heap layout.
| Input | Retained values | Decision |
|---|---|---|
12 | 12 | Space available |
4 | 4, 12 | Space available |
19 | 4, 12, 19 | Space available |
7 | 7, 12, 19 | Replace minimum 4 |
25 | 12, 19, 25 | Replace minimum 7 |
18 | 18, 19, 25 | Replace minimum 12 |
The final loop drains the heap in ascending order. Duplicate values are allowed and count as separate retained items. An input tied with the current minimum can be discarded because replacing one equal value would not change the result. If k exceeds the input length, we return all values in ascending order; an empty input returns an empty list.
Our top-k algorithm stores at most k candidates. For N inputs and k ≥ 2, selection takes O(N log k) time, followed by O(k log k) to emit up to k sorted results. More precisely, replace k in the emission cost with min(k, N); when k = 1, the scan is O(N). The retained heap needs O(min(k, N)) space, and the returned list needs that much space too.
What problems can Heaps solve?
Scheduling Events by Priority
A simulation can keep pending events in a min-heap ordered by their scheduled time. Removing the root selects the earliest event; processing it may insert more events. The heap supports this changing set without sorting all pending events after every update.
For application jobs, define priority explicitly. A smaller deadline might come first, while a larger urgency score might come first. Equal-priority items need an additional sequence number if predictable arrival order matters. Repeatedly favoring urgent work can also delay lower-priority jobs; the heap implements the ordering, while the application decides whether that policy is acceptable.
Merging Sorted Streams
When several streams are already sorted, place the next available item from each stream in a min-heap. Remove the smallest item, emit it, and replace it with the next item from the same stream. The heap compares the current candidates without loading every remaining item into memory.
Retaining Extreme Values
The top-k example retains a small set of large values while processing a longer input. A min-heap makes the weakest retained value easy to replace. Reverse the comparison and heap orientation to retain the smallest values instead.
A heap is less useful when you need arbitrary lookups or a fully ordered view at every step. A FIFO queue better expresses arrival order. A sorted array can suit mostly fixed data with ordered traversal, while a balanced search tree supports ordered lookup and range queries that a plain heap does not.
Conclusion
A heap maintains parent-child priority order so an extreme value is available at the root. A binary heap adds a complete tree shape, allowing compact array storage and logarithmic paths for sifting after insertion or removal. It provides this access without keeping every value in sorted order.
The top-k example uses exactly that limited ordering: the root identifies the weakest retained candidate, so each new value can be accepted or discarded without sorting the entire input. Use the same reasoning when choosing a heap for another task: identify the priority, decide whether the minimum or maximum should come next, and check whether root access matches the operations you need.