Javascript heapsort algorithm

Heap sort is divided into two processes:

1. Build the heap.

The heap is essentially a complete binary tree, which must satisfy that the keyword of any non-leaf node in the tree is not greater than (or less than) the keyword of its left and right children (if any) node.

The heap is divided into: large root heap and small root heap. Ascending sort USES large root heap and descending sort USES small root heap.

If it is a large root heap, the node with the largest value is adjusted to the heap root by an adjustment function.

2. Save the heap root in the tail, and call the adjustment function on the remaining sequences. After adjustment, save the maximum heel in the tail -1 (-1, -2,...). - I), and then adjust the remaining sequence, and repeat the process until the sorting is completed.

//Adjustment function 

function headAdjust(elements, pos, len){

  //Saves the current node value 

  var swap = elements[pos];

  //Locate the left child of the current node 

  var child = pos * 2 + 1;

  //Recursion until there are no child nodes 

  while(child < len){

    //If the current node has a right child node, and the right child node is large, the right child node 
 is used
    //Compare to the current node 

    if(child + 1 < len && elements[child] < elements[child + 1]){

      child += 1;

    }

    //Compare the current node and the largest child node, and exchange the value if it is less than, and then locate the current node 

    //
 on the child node
    if(elements[pos] < elements[child]){

      elements[pos] = elements[child];

      pos = child;

      child = pos * 2 + 1;

    }

    else{

      break;

    }

    elements[pos] = swap;

  }

}

//Build heap 

function buildHeap(elements){

  //Start with the last node that has a child node and compare that node with its children, 

  //The largest number is exchanged with the node, after which, the forward node in turn is exchanged for the same processing, 

  //Until the big top heap is built (ascending to big top, descending to small top) 

  for(var i=elements.length/2; i>=0; i--){

    headAdjust(elements, i, elements.length);

  }

}

function sort(elements){

  //Build heap 

  buildHeap(elements);

  //Adjust 
 from the end of the sequence
  for(var i=elements.length-1; i>0; i--){

    //The top of the heap is always the largest element, so swap the top and tail elements to 

    //The largest element is saved at the end and does not participate in subsequent adjustments 

    var swap = elements[i];

    elements[i] = elements[0];

    elements[0] = swap;

    //Adjust the maximum) element to the top of the heap 

    headAdjust(elements, 0, i);

  }

}

var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];

console.log('before: ' + elements);

sort(elements);

console.log(' after: ' + elements);

Efficiency:

Time complexity: best: O(nlog2n), worst: O(nlog2n), average: O(nlog2n).

Space complexity: O(1).

Stability: unstable