Heapify Array

heapify_array.js

//converting an array to a heap is performed with two functions, heapify and siftDown.
//The result is an array representation of a max heap.
//A max heap is required to perform a heap sort. 

//Time Complexity: O(N). Although siftDown is O(log n), the overall runtime is O(N). 
//Good info here on time complexity: https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/
//Space Complexity: O(1) auxiliary space is 0 since the array is converted to a heap in place.
const heapify = (arr) => {

  //end is the last element of the array
  let end = arr.length - 1;
  //start with the last root node (i.e. not a leaf) which is always floor(endIndex / 2)
  //if there are 9 elements in array, then the first 4 are roots, the last 5 are leaves
  //if there are 10 elements in an array, the first 5 are roots, the last 5 are leaves
  let start = Math.floor((end) / 2);

  //iterate from the last root to the first root
  while(start >= 0){
    //sift nodes down, which means towards the root.
    arr = siftDown(arr, start, end);
    start -= 1;
  }
  
  return arr
}

const siftDown = (arr, start, end) => {
  let root = start;
  //loop as long as the first child of the root is smaller than the array
  while((2 * root + 1) <= end) {
    //the first child of a node is always 2 * root + 1, the second child is 2 * root + 2
    let child = 2 * root + 1;
    
    //we are looking for the largest child
    if(child + 1 <= end && arr[child] < arr[child + 1]){
      child = child + 1;
    }
    
    //if the root is smaller than the larger of the two children, swap them
    if(arr[root] < arr[child]) {
      let tmp = arr[root];
      arr[root] = arr[child];
      arr[child] = tmp;
      
      //every time we swap a root with a child
      //check the new root's children to determine if another swap is needed.
      //This has the effect of 'sifting down' smaller elements towards the leaves.
      root = child;
    } else {
      return arr;
    }
  }
  return arr;
}

let arr = [4,56,2,0,6,6,6,14,9,99,6,6];

//output  [99,56,6,14,6,6,6,0,9,4,6,2]
console.log(heapify(arr));