Heap sort

by rishul matta

JavaScript

function left(i) {
  return 2 * i + 1;
}

function right(i) {
  return 2 * i + 2;
}

function heapify(A, i) {


  let length = A.length;
  let lef = left(i);
  let righ = right(i);
  let largestIndex = i;

  if (lef <= length && A[i] < A[lef]) { // note
    largestIndex = lef;
  }

  if (righ <= length && A[largestIndex] < A[righ]) {
    largestIndex = righ;
  }

  if (largestIndex != i) {
    let swap = A[i];
    A[i] = A[largestIndex];
    A[largestIndex] = swap;
    heapify(A, largestIndex);
  }


}


function buidHeap(A) {
  for (let i = Math.floor(A.length / 2); i >= 0; --i) {
    heapify(A, i);
  }

  return A;
}


function heapSort(A) {
  buidHeap(A);
  let B = [];
  while (A.length) {
    B.push(A.shift());
    debugger;
    const element = A.pop();
    if (element !== undefined) { // Note this
    	A.unshift(element)
    	heapify(A, 0);
    }

  }
  return B;
}

console.log(heapSort([5, 4, 6, 10, 2, 55]))