class MinHeap {
constructor() {
this.heap = []
}
getLeftIndex(index) {
return 2 * index + 1
}
getRightIndex(index) {
return 2 * index + 2
}
getParentIndex(index) {
if (index === 0) {
return undefined
}
return Math.floor((index - 1) / 2)
}
insert(value) {
if (value != null) {
this.heap.push(value);
this.siftUp(this.heap.length - 1)
return true;
}
return false
}
siftUp(index) {
let parent = this.getParentIndex(index);
while (index > 0 && this.heap[parent] > this.heap[index]) {
swap(this.heap, parent, index);
index = parent;
parent = this.getParentIndex(index)
}
}
siftDown(index) {
let element = index;
const left = this.getLeftIndex(index);
const right = this.getRightIndex(index);
const size = this.heap.length;
if(left < size && this.heap[element] > this.heap[left]) {
element = left
}
if(right < size && this.heap[element] > this.heap[right]) {
element = right
}
if (index !== element) {
swap(this.heap, index, element);
this.siftDown(element)
}
}
extract() {
if (this.heap.length === 0) {
return undefined
}
if (this.heap.length === 1) {
return this.heap.shift()
}
const removedNode = this.heap.shift();
this.siftDown(0);
return removedNode
}
}
function swap(arr, a, b) {
const temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
const heap = new MinHeap();
heap.insert(5)
heap.insert(4)
heap.insert(3)
heap.insert(2)
heap.insert(1)
console.log(heap.heap)