JAVASCRIPT

min heap javascript

// 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;
  }
}

what is a heap in javascript

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.

heap javascript

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;
    
  
  }
  
}