Heap-like Data Structures Mind Map
Algorithm & Systems VisualizationsEvery heap-like data structures visualization on this site on one map. The branches are the main ideas. Each leaf is a page; the grey line under it is the one thing to remember about it. Click a branch to focus on it, click a page to open it.
1. How the map is organized
Ask how the heap is stored and what it does fast:
- One tree or many? One complete tree in an array is a binary heap. A list of heap-ordered trees is a heap forest.
- Is merge the core step? If insert and remove-min are both built from merging two trees along their right spines, it is a merge-based heap.
- Which cost matters? If you need many decrease-keys (as in Dijkstra), compare them: the Fibonacci heap wins on paper.
2. The branches side by side
| Branch | Insert | Remove-min | Merge two heaps |
|---|---|---|---|
| Binary heap | O(log n) | O(log n) | O(n), rebuild |
| Leftist heap | O(log n) | O(log n) | O(log n) |
| Skew heap | O(log n) amortized | O(log n) amortized | O(log n) amortized |
| Binomial queue | O(1) amortized | O(log n) | O(log n) |
| Fibonacci heap | O(1) | O(log n) amortized | O(1) |
3. Five facts to remember
- Heap order: every parent is no larger than its children, so the minimum is at a root.
- A binary heap stores node i's children at 2i + 1 and 2i + 2, with no pointers.
- BuildHeap turns an array into a heap in O(n), not O(n log n).
- A binomial queue with n items has one tree of size 2ᵏ for each 1 bit of n.
- Fibonacci heaps make decrease-key O(1) amortized, giving Dijkstra O(E + V log V).
See all heap-like data structures pages in the index, or the other mind maps.