Array Representation of Heap
Min Heap: Insert 1
- Add the element at the end.
- Heapify-Up from the last index.
class MinHeap {
constructor() {
this.heap = [5, 10, 20, 30];
}
getLeftChildIndex(i) { return (2 * i) + 1; }
getRightChildIndex(i) { return (2 * i) + 2; }
getParentIndex(i) { return Math.floor((i - 1) / 2); }
insert(val) {
this.heap.push(val);
let lastIndex = this.heap.length - 1;
this.heapifyUp(lastIndex);
}
heapifyUp(i) {
while (i > 0) {
let parentIndex = this.getParentIndex(i);
if (this.heap[i] < this.heap[parentIndex]) {
[this.heap[i], this.heap[parentIndex]] =
[this.heap[parentIndex], this.heap[i]];
i = parentIndex;
} else break;
}
}
}
let heap = new MinHeap();
heap.insert(1);
console.log(heap.heap);
Dry Run
Input: Initial heap = [5, 10, 20, 30], Insert value = 1
Step 0: Start Function insert(1) into heap [5, 10, 20, 30] Step 1: Push 1 at the end heap = [5, 10, 20, 30, 1] lastIndex = 4 Step 2: Call heapifyUp(4) i = 4 → parentIndex = 1 Compare 1 < 10 → swap heap = [5, 1, 20, 30, 10] i = 1 → parentIndex = 0 Compare 1 < 5 → swap heap = [1, 5, 20, 30, 10] i = 0 → loop ends Step 3: End Return heap = [1, 5, 20, 30, 10]
Final Output: [1, 5, 20, 30, 10]
Final State: heap = [1, 5, 20, 30, 10]
