Binary heap:- A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:
the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.
let MinHeap = function() {
let head = [null];
this.insert = function(element) {
head.push(element);
if (head.length > 2) {
let idx = head.length - 1;
while (head[idx] < head[Math.floor(idx / 2)]) {
if (idx >= 1) {
[head[Math.floor(idx / 2)], head[idx]] = [head[idx], head[Math.floor(idx / 2)]];
if (Math.floor(idx / 2) > 1) {
idx = Math.floor(idx / 2);
} else {
break;
}
}
}
}
}
}
let minHeap = new MinHeap();
minHeap.insert(2)
minHeap.insert(1)
minHeap.insert(3)
minHeap.insert(4)
let MaxHeap = function() {
let head = [null];
this.insert = function(element) {
head.push(element);
if (head.length > 2) {
let idx = head.length - 1;
while (head[idx] > head[Math.floor(idx / 2)]) {
if (idx >= 1) {
[head[Math.floor(idx / 2)], head[idx]] = [head[idx], head[Math.floor(idx / 2)]];
if (Math.floor(idx / 2) > 1) {
idx = Math.floor(idx / 2);
} else {
break;
}
}
}
}
}
}
let maxHeap = new MaxHeap();
maxHeap.insert(2)
maxHeap.insert(1)
maxHeap.insert(3)
maxHeap.insert(4)
Any comments or suggestions are welcome.
Top comments (0)