// Aim is to build a min-heap from an
// array of integers with support for following methods:
// buildHeap(array): to build the heap from array
// bubbleDown(currentIdx, endIdx, heap): to bubble an element down
// bubbleUp(currentIdx, heap): to bubble an element up
// peek(): returns min value without removing it
// remove(): removes min value
// insert(): inserts a new element into heap
class MinHeap {
// Build heap using array of ints
constructor(array) {
this.heap = this.buildHeap(array);
}
// O(n) time | O(1) space
buildHeap(array) {
const firstParentIdx = Math.floor((array.length - 2) / 2);
for (let currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
this.bubbleDown(currentIdx, array.length - 1, array);
}
return array;
}
// O(log(n)) time | O(1) space
bubbleDown(currentIdx, endIdx, heap) {
let childOneIdx = currentIdx * 2 + 1;
while (childOneIdx <= endIdx) {
const childTwoIdx =
currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
let idxToSwap;
if (childTwoIdx !== -1 && heap[childTwoIdx] < heap[childOneIdx]) {
idxToSwap = childTwoIdx;
} else {
idxToSwap = childOneIdx;
}
if (heap[idxToSwap] < heap[currentIdx]) {
this.swap(currentIdx, idxToSwap, heap);
currentIdx = idxToSwap;
childOneIdx = currentIdx * 2 + 1;
} else {
return;
}
}
}
// O(log(n)) time | O(1) space
bubbleUp(currentIdx, heap) {
let parentIdx = Math.floor((currentIdx - 1) / 2);
while (currentIdx > 0 && heap[currentIdx] < heap[parentIdx]) {
this.swap(currentIdx, parentIdx, heap);
currentIdx = parentIdx;
parentIdx = Math.floor((currentIdx - 1) / 2);
}
}
// O(1) time | O(1) space
peek() {
return this.heap[0];
}
// O(log(n)) time | O(1) space
remove() {
this.swap(0, this.heap.length - 1, this.heap);
const valueToRemove = this.heap.pop();
this.bubbleDown(0, this.heap.length - 1, this.heap);
return valueToRemove;
}
// O(log(n)) time | O(1) space
insert(value) {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1, this.heap);
}
swap(i, j, heap) {
const temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
}
heap is a binary tree where each node is greater than both its leaves.
The tree itself is complete or nearly complete at all times,
so the heap is backed by a compact array.
When values are added or removed, the tree rotates until the value has
sunk until its parent is greater, or floated until all children are less.
class Heap{
constructor(capacity, heap_type)
{
this.heap_type = heap_type;
this.count = 0;
this.capacity = capacity;
this.array = [];
}
Parent()
{
if(i<= 0 || i>=this.count)
{return -1;}
return i-1/2;
}
LeftChildren(i)
{
left = 2*i +1;
if(left >= this.count)
{
return -1;
}
return left;
}
GetMaximum()
{
if(this.count == 0)
{
return -1;
}
return this.array[0];
}
PercolateDown(i){
var i, r, max, temp;
l = LeftChild(i);
r = RightChild(i);
if(l != -1 && this.array[r] > this.array[max])
{
max = r;
}
if(max != i)
{
temp = this.array[i];
this.array[i] = this.array[max];
max = r;
}
if(max != i){
temp = this.array[i];
this.array[i] = this.array[max];
this.array[max] = temp;
}
PercolateDown(max);
}
DeleteMax()
{
if(this.count == 0)
{
return -1;
}
data = this.array[0];
this.array[0] = this.array[this.count-1];
this.count --;
PercolateDown(0);
return data;
}
Insert(data)
{
i;
if(this.count == this.capacity)
{
ResizeHeap();
}
this.count++;
while(i>=0 && data >this.array[(i-1)/2]){
this.array[i] = this.array[(i-1)/2];
i = i-1/2;
}
this.array[i] = data;
}
ResizeHeap()
{
this.array = [...this.array]
if(this.array == null)
{console.log("Memory Error)
return;
}
for(i =0; i<this.capacity; i++)
{
this.array[i] = array_old[i];
}
this.capacity *=2;
array_old =null
}
Heapsort(A, n)
{
h = new Heap(n,0);
var old_size, i, temp;
BuildHeap(h, A, n);
old_size = h.count;
for(i = n-1 ; i>0; i--)
{
temp = h.array[0];
h.array[0] = h.array[h.count-1];
h.count--;
h.PercolateDown(0);
}
h.count = old_size;
}
}
heap is a binary tree where each node is greater than both its leaves.
The tree itself is complete or nearly complete at all times,
so the heap is backed by a compact array.
When values are added or removed, the tree rotates until the value has
sunk until its parent is greater, or floated until all children are less.