Detailed explanation of Javascript heap sort algorithm

This article mainly introduces the Javascript heap sorting algorithm and its examples. It is very practical. Friends in need can refer to it.

Heap sorting is divided into two processes:

1. Build a heap.

A heap is essentially a complete binary tree, which must satisfy: the keyword of any non-leaf node in the tree is not greater than (or not less than) the keyword of its left and right child nodes (if they exist).

The heap is divided into: large root heap and small root heap. The large root heap is used for ascending sorting, and the small root heap is used for descending sorting.

If it is a large root heap, adjust the node with the largest value to the root of the heap through the adjustment function.

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

//调整函数
function headAdjust(elements, pos, len){
  //将当前节点值进行保存
  var swap = elements[pos];
  //定位到当前节点的左边的子节点
  var child = pos * 2 + 1;
  //递归，直至没有子节点为止
  while(child < len){
    //如果当前节点有右边的子节点，并且右子节点较大的场合，采用右子节点
    //和当前节点进行比较
    if(child + 1 < len && elements[child] < elements[child + 1]){
      child += 1;
    }
    //比较当前节点和最大的子节点，小于则进行值交换，交换后将当前节点定位
    //于子节点上
    if(elements[pos] < elements[child]){
      elements[pos] = elements[child];
      pos = child;
      child = pos * 2 + 1;
    }
    else{
      break;
    }
    elements[pos] = swap;
  }
}
//构建堆
function buildHeap(elements){
  //从最后一个拥有子节点的节点开始，将该节点连同其子节点进行比较，
  //将最大的数交换与该节点,交换后，再依次向前节点进行相同交换处理，
  //直至构建出大顶堆（升序为大顶，降序为小顶）
  for(var i=elements.length/2; i>=0; i--){
    headAdjust(elements, i, elements.length);
  }
}
function sort(elements){
  //构建堆
  buildHeap(elements);
  //从数列的尾部开始进行调整
  for(var i=elements.length-1; i>0; i--){
    //堆顶永远是最大元素，故，将堆顶和尾部元素交换，将
    //最大元素保存于尾部，并且不参与后面的调整
    var swap = elements[i];
    elements[i] = elements[0];
    elements[0] = swap;
    //进行调整，将最大）元素调整至堆顶
    headAdjust(elements, 0, i);
  }
}
var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log(&#39;before: &#39; + elements);
sort(elements);
console.log(&#39; after: &#39; + elements);

Efficiency:

Time complexity: Best: O(nlog2n), Worst: O(nlog2n), Average: O(nlog2n).

Space complexity: O(1).

Stability: Unstable

The above is the entire content of this chapter. For more related tutorials, please visit JavaScript Video Tutorial!