Implementing Heap Insert
What you'll learn: You'll learn how to code the insertion operation for a binary heap using index arithmetic to navigate the array-based tree structure.
The Core Mechanism
When inserting a new element into a heap, you add it at the next available position (maintaining the complete binary tree property), then "bubble it up" by repeatedly swapping with its parent until the heap order property is restored. The key is using the parent-child index formulas you've already learned.
Step-by-Step Implementation
Given an array-based heap with the next insertion index n:
- Place the new value at index
n(the next open spot) - Set current index
i = n - Calculate parent index:
parent = (i - 1) // 2(integer division) - Compare
heap[i]withheap[parent] - If heap order violated (e.g., in a min-heap, child < parent):
- Swap
heap[i]andheap[parent] - Set
i = parent - Repeat from step 3
- Swap
- Stop when heap order is satisfied or you reach the root (
i == 0)
Example (Min-Heap)
Inserting 5 into heap [10, 15, 20, 30, 25]:
- Place
5at index 5:[10, 15, 20, 30, 25, 5] - Parent of index 5 is
(5-1)//2 = 2(value 20) 5 < 20, so swap:[10, 15, 5, 30, 25, 20]- Now at index 2, parent is
(2-1)//2 = 0(value 10) 5 < 10, so swap:[5, 15, 10, 30, 25, 20]- At index 0 (root), stop
Key Takeaway: Heap insert uses the parent formula (i - 1) // 2 to bubble the new element upward through swaps until the heap order property is satisfied, maintaining both shape and order invariants.