Deleting (Extracting) Elements from a Heap
Min Heap:
- Extraction only happen
from the top= heap[0].
- Heapify down is the process of
restoring the heap propertyafter removing the root element (or moving an element downwards). MinHeap is formed.
Practice:
Solution:
Min Heapis formed.
Code
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;
}
}
extract () {
if(this.heap.length < 1) return null;
let min = this.heap[0];
let lastIndex = this.heap.length - 1;
[this.heap[0], this.heap[lastIndex]] = [this.heap
[lastIndex], this.heap[0]];
this.heap.pop();
this.heapifyDown(0);
return min;
}
heapifyDown(i){
let left = this.getLeftChildIndex(i);
let right = this.getRightChildIndex(i);
let n = this.heap.length;
let smallest = i;
if(left < n && this.heap[left] < this.heap[smallest]) {
smallest = left;
}
if(right < n && this.heap[right] < this.heap[smallest]) {
smallest = right;
}
if(smallest != i){
[this.heap[smallest], this.heap[i]] = [this.heap[i],this.heap[smallest]];
this.heapifyDown(smallest);
}
}
// peek operation
peek() {
if(!this.heap.length) return null;
return this.heap[0];
}
}
let heap = new MinHeap();
heap.insert(5);
heap.insert(20);
heap.insert(4);
heap.insert(10);
heap.insert(1);
heap.insert(0);
console.log(heap.peek());
console.log(heap.extract());
console.log(heap.extract());
console.log(heap.heap);
Dry Run
Input:
Initial heap = [5, 10, 20, 30] Insert value = 5
State Transitions:
Step 1: Call insert(5) → push(5) → heap = [5, 10, 20, 30, 5] → lastIndex = 4 Step 2: heapifyUp(4) i = 4 → parentIndex = 1 → Compare 5 < 10 → swap → [5, 5, 20, 30, 10] i = 1 → parentIndex = 0 → Compare 5 < 5 → false → break
Final Output: [5, 5, 20, 30, 10]
Final State: heap = [5, 5, 20, 30, 10]
Input:
heap = [5, 5, 20, 30, 10] Insert value = 20
State Transitions:
Step 1: Call insert(20) → push(20) → heap = [5, 5, 20, 30, 10, 20] → lastIndex = 5 Step 2: heapifyUp(5) i = 5 → parentIndex = 2 → Compare 20 < 20 → false → break
Final Output: [5, 5, 20, 30, 10, 20]
Final State: heap = [5, 5, 20, 30, 10, 20]
Input:
heap = [5, 5, 20, 30, 10, 20] Insert value = 4
State Transitions:
Step 1: Call insert(4) → push(4) → heap = [5, 5, 20, 30, 10, 20, 4] → lastIndex = 6 Step 2: heapifyUp(6) i = 6 → parentIndex = 2 → Compare 4 < 20 → swap → [5, 5, 4, 30, 10, 20, 20] i = 2 → parentIndex = 0 → Compare 4 < 5 → swap → [4, 5, 5, 30, 10, 20, 20] i = 0 → loop ends
Final Output: [4, 5, 5, 30, 10, 20, 20]
Final State: heap = [4, 5, 5, 30, 10, 20, 20]
Input:
heap = [4, 5, 5, 30, 10, 20, 20] Insert value = 10
State Transitions:
Step 1: Call insert(10) → push(10) → heap = [4, 5, 5, 30, 10, 20, 20, 10] → lastIndex = 7 Step 2: heapifyUp(7) i = 7 → parentIndex = 3 → Compare 10 < 30 → swap → [4, 5, 5, 10, 10, 20, 20, 30] i = 3 → parentIndex = 1 → Compare 10 < 5 → false → break
Final Output: [4, 5, 5, 10, 10, 20, 20, 30]
Final State: heap = [4, 5, 5, 10, 10, 20, 20, 30]
Input:
heap = [4, 5, 5, 10, 10, 20, 20, 30] Insert value = 1
State Transitions:
Step 1: Call insert(1) → push(1) → heap = [4, 5, 5, 10, 10, 20, 20, 30, 1] → lastIndex = 8 Step 2: heapifyUp(8) i = 8 → parentIndex = 3 → Compare 1 < 10 → swap → [4, 5, 5, 1, 10, 20, 20, 30, 10] i = 3 → parentIndex = 1 → Compare 1 < 5 → swap → [4, 1, 5, 5, 10, 20, 20, 30, 10] i = 1 → parentIndex = 0 → Compare 1 < 4 → swap → [1, 4, 5, 5, 10, 20, 20, 30, 10] i = 0 → loop ends
Final Output: [1, 4, 5, 5, 10, 20, 20, 30, 10]
Final State: heap = [1, 4, 5, 5, 10, 20, 20, 30, 10]
Input:
heap = [1, 4, 5, 5, 10, 20, 20, 30, 10] Insert value = 0
State Transitions:
Step 1: Call insert(0) → push(0) → heap = [1, 4, 5, 5, 10, 20, 20, 30, 10, 0] → lastIndex = 9 Step 2: heapifyUp(9) i = 9 → parentIndex = 4 → Compare 0 < 10 → swap → [1, 4, 5, 5, 0, 20, 20, 30, 10, 10] i = 4 → parentIndex = 1 → Compare 0 < 4 → swap → [1, 0, 5, 5, 4, 20, 20, 30, 10, 10] i = 1 → parentIndex = 0 → Compare 0 < 1 → swap → [0, 1, 5, 5, 4, 20, 20, 30, 10, 10] i = 0 → loop ends
Final Output: [0, 1, 5, 5, 4, 20, 20, 30, 10, 10]
Final State: heap = [0, 1, 5, 5, 4, 20, 20, 30, 10, 10]
Operation: peek()
Output = 0
Operation: extract()
Initial heap = [0, 1, 5, 5, 4, 20, 20, 30, 10, 10] Swap heap[0] with heap[9] → [10, 1, 5, 5, 4, 20, 20, 30, 10, 0] Pop → heap = [10, 1, 5, 5, 4, 20, 20, 30, 10] heapifyDown(0): → left = 1, right = 2, smallest = 1 → swap → [1, 10, 5, 5, 4, 20, 20, 30, 10] → i = 1: left = 3, right = 4, smallest = 4 → swap → [1, 4, 5, 5, 10, 20, 20, 30, 10] → i = 4: left = 9, right = 10 → out of range → stop
Extracted: 0
Final heap: [1, 4, 5, 5, 10, 20, 20, 30, 10]
Operation: extract()
Initial heap = [1, 4, 5, 5, 10, 20, 20, 30, 10] Swap heap[0] with heap[8] → [10, 4, 5, 5, 10, 20, 20, 30, 1] Pop → heap = [10, 4, 5, 5, 10, 20, 20, 30] heapifyDown(0): → left = 1, right = 2, smallest = 1 → swap → [4, 10, 5, 5, 10, 20, 20, 30] → i = 1: left = 3, right = 4, smallest = 3 → swap → [4, 5, 5, 10, 10, 20, 20, 30] → i = 3: left = 7, right = 8 → out of range → stop
Extracted: 1
Final heap: [4, 5, 5, 10, 10, 20, 20, 30]
