Detailed graphic explanation of Heap Sort heap sorting algorithm and JavaScript code implementation_Basic knowledge

1. I have to talk about binary trees
To understand the heap, you must first understand the binary tree. In computer science, a binary tree is a tree structure in which each node has at most two subtrees. Usually subtrees are called "left subtree" and "right subtree". Binary trees are often used to implement binary search trees and binary heaps.
Each node of a binary tree has at most two subtrees (there are no nodes with degree greater than 2). The subtrees of a binary tree are divided into left and right subtrees, and the order cannot be reversed. The i-th level of a binary tree has at most 2i - 1 nodes; a binary tree with depth k has at most 2k - 1 nodes; for any binary tree T, if the number of terminal nodes is n0, the number of nodes with degree 2 is n2, then n0 = n2 + 1.
Three main differences between trees and binary trees:
The number of nodes of a tree must be at least 1, while the number of nodes of a binary tree can be 0
There is no limit to the maximum degree of a node in a tree, while the maximum degree of a node in a binary tree is 2
The nodes of the tree are not divided into left and right, while the nodes of the binary tree are divided into left and right
Binary trees are divided into complete binary trees and full binary trees
Full binary tree: A tree with depth k and 2k - 1 nodes is called a full binary tree

(full binary tree with depth 3)
Complete binary tree: A binary tree with depth k and n nodes. If and only if each of its nodes corresponds to the nodes numbered 1 to n in the full binary tree with depth k, it is called a complete binary tree

(complete binary tree with depth 3)
2. What is a heap?
A heap (binary heap) can be regarded as a complete binary tree. An "excellent" property of a complete binary tree is that every level except the lowest level is full, which allows the heap to use arrays to Represented (ordinary binary trees are usually represented by linked lists as basic containers), each node corresponds to an element in the array.
As shown below, it is the relationship between a heap and an array

(Interrelationship between heap and array)
For a given subscript i of a node, the subscripts of the parent node and child node of this node can be easily calculated:
Parent(i) = floor(i/2), i’s parent node subscript
Left(i) = 2i, the subscript of the left child node of i
Right(i) = 2i + 1, i’s right child node subscript

Binary heaps are generally divided into two types: maximum heap and minimum heap.
Maximum heap:
The maximum element value in the max heap appears at the root node (top of the heap)
The element value of each parent node in the heap is greater than or equal to its child node (if it exists)

(maximum heap)
Minimum heap:
The smallest element value in the min-heap appears at the root node (top of the heap)
The element value of each parent node in the heap is less than or equal to its child node (if it exists)

(min heap)
3. Heap sorting principle
Heap sorting is to take out the maximum number at the top of the maximum heap, continue to adjust the remaining heap to the maximum heap, and take out the maximum number at the top of the heap again. This process continues until there is only one remaining number. Define the following operations on the heap:
Max-Heapify: Adjust the end child nodes of the heap so that the child nodes are always smaller than the parent node
Create a maximum heap (Build-Max-Heap): Reorder all data in the heap to make it a maximum heap
Heap-Sort: Remove the root node of the first data and perform a recursive operation of maximum heap adjustment
Before continuing with the following discussion, one thing that needs to be noted is that arrays are all Zero-Based, which means that our heap data structure model will change

（Zero-Based）
Correspondingly, several calculation formulas must also be adjusted accordingly:
Parent(i) = floor((i-1)/2), i’s parent node subscript
Left(i) = 2i + 1, i’s left child node subscript
Right(i) = 2(i + 1), i’s right child node subscript
The function of maximum heap adjustment (MAX-HEAPIFY) is to maintain the properties of the maximum heap and is the core subroutine for creating the maximum heap. The function process is as shown in the figure:

(Max-Heapify)
Since after one adjustment, the heap still violates the heap properties, recursive testing is required to make the entire heap satisfy the heap properties. This can be expressed in JavaScript as follows:

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax = index,
   iLeft = 2 * index + 1,
   iRight = 2 * (index + 1);

 if (iLeft < heapSize && array[index] < array[iLeft]) {
  iMax = iLeft;
 }

 if (iRight < heapSize && array[iMax] < array[iRight]) {
  iMax = iRight;
 }

 if (iMax != index) {
  swap(array, iMax, index);
  maxHeapify(array, iMax, heapSize); // 递归调整
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

Generally speaking, recursion is mainly used in the divide and conquer method, but divide and conquer is not required here. Moreover, recursive calls require pushing/clearing the stack, which has a slight performance disadvantage compared with iteration. Of course, following the 20/80 rule, this can be ignored. But if you feel that using recursion will make you feel uncomfortable, you can also use iteration, such as the following:

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax, iLeft, iRight;
 while (true) {
  iMax = index;
  iLeft = 2 * index + 1;
  iRight = 2 * (index + 1);
  if (iLeft < heapSize && array[index] < array[iLeft]) {
   iMax = iLeft;
  }

  if (iRight < heapSize && array[iMax] < array[iRight]) {
   iMax = iRight;
  }

  if (iMax != index) {
   swap(array, iMax, index);
   index = iMax;
  } else {
   break;
  }
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

The function of creating a maximum heap (Build-Max-Heap) is to transform an array into a maximum heap. It accepts two parameters: array and heap size. Build-Max-Heap will call Max-Heapify from bottom to top. Transform the array and create a maximum heap. Because Max-Heapify can ensure that the nodes after the node with subscript i satisfy the maximum heap property, bottom-up calling Max-Heapify can maintain this property during the transformation process. If the number of elements in the maximum heap is n, then Build-Max-Heap starts from Parent(n) and calls Max-Heapify upwards. The process is as follows:

Described in JavaScript as follows:

function buildMaxHeap(array, heapSize) {
 var i,
   iParent = Math.floor((heapSize - 1) / 2);
   
 for (i = iParent; i >= 0; i--) {
  maxHeapify(array, i, heapSize);
 }
}

Heap-Sort is the interface algorithm of heap sort. Heap-Sort first calls Build-Max-Heap to transform the array into a maximum heap, then exchanges the top and bottom elements of the heap, then raises the bottom, and finally Recall Max-Heapify to maintain the maximum heap properties. Since the top element of the heap must be the largest element in the heap, after one operation, the largest element existing in the heap is separated from the heap. After repeating n-1 times, the array is arranged. The whole process is as follows:

Described in JavaScript as follows:

function heapSort(array, heapSize) {

 buildMaxHeap(array, heapSize);

 for (int i = heapSize - 1; i > 0; i--) {
  swap(array, 0, i);
  maxHeapify(array, 0, i);
 } 
}

4.JavaScript language implementation
Finally, organize the above into the complete javascript code as follows:

function heapSort(array) {

 function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
 }

 function maxHeapify(array, index, heapSize) {
  var iMax,
   iLeft,
   iRight;
  while (true) {
   iMax = index;
   iLeft = 2 * index + 1;
   iRight = 2 * (index + 1);

   if (iLeft < heapSize && array[index] < array[iLeft]) {
    iMax = iLeft;
   }

   if (iRight < heapSize && array[iMax] < array[iRight]) {
    iMax = iRight;
   }

   if (iMax != index) {
    swap(array, iMax, index);
    index = iMax;
   } else {
    break;
   }
  }
 }

 function buildMaxHeap(array) {
  var i,
   iParent = Math.floor(array.length / 2) - 1;

  for (i = iParent; i >= 0; i--) {
   maxHeapify(array, i, array.length);
  }
 }

 function sort(array) {
  buildMaxHeap(array);

  for (var i = array.length - 1; i > 0; i--) {
   swap(array, 0, i);
   maxHeapify(array, 0, i);
  }
  return array;
 }

 return sort(array);
}

5. Application of heap sort algorithm

(1) Algorithm performance/complexity
The time complexity of heap sort is very stable (we can see that it is not sensitive to the input data), and is O(n㏒n) complexity. The best case is the same as the worst case.
However, its space complexity varies from implementation to implementation. Two common complexities have been discussed above: O(n) and O(1). In line with the principle of saving space, I recommend the O(1) complexity method.

(2) Algorithm stability
Heap sorting involves a large number of screening and moving processes and is an unstable sorting algorithm.

(3) Algorithm applicable scenarios
Heap sorting will cause relatively large overhead in the process of establishing and adjusting the heap, and is not suitable when there are few elements. However, it is still a good choice when there are many elements. Especially when solving problems such as "the first n largest numbers", it is almost the preferred algorithm.