What is a heap?
A heap is a complete binary tree stored in an array that keeps one special value at the root: the smallest in a min-heap, the largest in a max-heap. Every parent is ordered against its children, but siblings are not sorted.
The children of index i live at 2i+1 and 2i+2, so no pointers are needed. Insert adds at the end and bubbles up. Extract moves the last value to the root and sinks it down. Heaps back priority queues and heap sort.
Time complexity
| Operation | Time | Notes |
|---|---|---|
| Insert | O(log n) | Bubble up at most the height of the tree |
| Extract root | O(log n) | Sink down at most the height of the tree |
| Peek root | O(1) | The root is always the min or max |
| Build from n values | O(n) | With bottom-up heapify |
Try it yourself
- Insert small values into a min-heap and watch them bubble up.
- Extract the root and watch the last value sink down.
- Switch to Max-heap to see the root become the largest value.
- Press Display heap to print the array in level order.
Heap vs sorted array
A sorted array finds the minimum instantly but needs O(n) to insert. A heap gives O(log n) for both insert and extract, which is why it is the usual choice for priority queues.
Common questions
- What is the difference between a min-heap and a max-heap?
- A min-heap keeps the smallest value at the root. A max-heap keeps the largest value at the root.
- Is a heap the same as a binary search tree?
- No. A heap only orders parents against children, so it finds the min or max quickly but cannot search for arbitrary values efficiently.
- Why is a heap stored in an array?
- Because it is a complete tree, positions fill level by level, so parent and child indices can be calculated instead of stored as pointers.