Heap Operations
Heap operations are how a binary heap keeps its structure during insert and extract-max.
HEAP
Nothing in the heap
Size
0
Swaps
0
At most
0
7 values to insert, one at a time: 10, 20, 15, 30, 40, 5, 25. Each lands in the first free slot and climbs until its parent is no smaller than its children — never further than the tree's height, which is the whole of why an insert is O(log n) no matter how much is already in there.
Next
10 is the first value, so it goes to index 0 and it is the root. Nothing to compare it against and nowhere to climb.
Value (0–99)
Intuition
Maintaining the heap property requires re-shuffling elements when the tree changes.
When we Insert, we add to the end and "bubble up" (swim) to find the correct spot. When we Extract Max, we replace the root with the last element and "bubble down" (sink) to fix the order.
Concept
Heapify Logic:
- Swim (Shift-Up): Swap node with parent if it violates heap property. Repeat until root or correct.
- Sink (Shift-Down): Swap node with largest child if it violates heap property. Repeat until leaf or correct.
How it Works
The figure opens by inserting 10, 20, 15, 30, 40, 5 and 25 into an empty max-heap, the same structure as the MaxHeap class below. It draws the heap twice: as a tree, and as the array that actually holds it, with each index under its cell, so a parent at index i can be checked against its children at 2i + 1 and 2i + 2.
- Insert: The value lands at the end of the array and swims up while it is larger than its parent. In the opening build 20, 30, 40 and 25 move, 6 swaps in all.
- Extract: The root comes out, the last leaf moves into index 0, and it sinks while a child is larger. On the opening heap this returns 40 in 2 swaps.
- Swaps and At most: The swap count of each operation sits beside the height of the tree, the most it can cost.
- Ordering and presets: Switch between MAX and MIN, or rebuild from Mixed, Climb or Dive, to watch the same values cost a different number of swaps.
Step-by-Step Breakdown
1. insert(val): push val onto the end of the array, then swim from the last index.
2. extractMax(): keep heap[0], move the last element into index 0, then sink from index 0.
3. swim(k): while k is above 0, stop if the parent is at least as large as heap[k]; otherwise swap them and continue from the parent.
4. sink(k): while k has a child, pick the larger child; stop if heap[k] is at least as large; otherwise swap them and continue from that child.
When to Use
- Implementing a Priority Queue.
- Streaming algorithms (median of data stream).
- Graph algorithms (Prim's, Dijkstra's).
When NOT to Use
- When you need to search for an arbitrary value (requires O(N) scan).
- When standard Sorting is sufficient.
How to Identify
"Dynamic inserts and get max", "Process elements by importance".
Applying for software engineering roles? Free, no sign-up: