start

Heap sort is a complex sorting algorithm, which mainly uses the data structure Heap.

Heap is a kind of binary tree, complete binary tree, it is characterized by:

  • All layer nodes are full except for the last layer
  • The last layer of nodes can be dissatisfied
  • The last layer of nodes is filled from left to right
  • There is no limit to the size relationship between the left node and the right node

The following figure

The heap is divided into

  • MaxHeap, the parent node value is greater than the child node value
  • MinHeap, the value of the parent node is less than the value of the child node

The main process for heap sorting (using MaxHeap as an example) :

  • Construct the array as MaxHeap with the maximum parent node
  • Swap the parent node with the trailing element,
  • Rebuild the remaining elements again as MaxHeap
  • Repeat two or three steps until there is only one element left

The process of constructing MaxHeap

The key process is shiftDown from the first non-leaf node to the top and right to the left.

Where, Heap can be represented by an array structure, node index I is known, and its node relationship is

  • Parent node, math.floor ((i-1) / 2)
  • Left node, 2 times I plus 1
  • The right node, 2 times I plus 2
  • The first non-leaf node, arr. Length / 2-1

Recommend for

Some implementations are given in the reference. However, for the heapifyDown method, the following implementation is recommended, which comes from reference 4. Personally, I think it is better in terms of understanding and structure.

  heapifyDown(customStartIndex = 0) {
    // Compare the parent element to its children and swap parent with the appropriate
    // child (smallest child for MinHeap, largest child for MaxHeap).
    // Do the same forNext children after swap. // When using Heap sorting, the top element is assigned to the bottom element, and the Heap needs to be rebuilt from top to bottomlet currentIndex = customStartIndex;
    letnextIndex = null; // In the MaxHeap, the initial relationship of nodes is P->C->C1, and the heap is constructed first. // Continue to assume that the child node C is greater than the parent node P, then the child node C needs to be switched with the parent node P, and the parent node P is sunk as the child node. // If C1>P, the node P needs to be lowered to C->C1->P. // If C1>P, the node P needs to be lowered to C->C1->P. // If C1>P, the node P should be lowered to C->C1->PwhileThe loop is the path, although there is only one parameter customStartIndex above, but considering that // nodes may be interchangeable, we need to recurse downward, comparing all nodes of the current node at oncewhile(this.hasleftChild (currentIndex)) {// Unlike binary trees, the relationship between the left and right nodes in the Heap structure is not fixed // The left node may be smaller than the right node or larger than the right node, The value of the left/right node and the parent node can only be greater than that of the fixed relationshipinThe value of Heap is swapped with the parentif (
        this.hasRightChild(currentIndex)
        && this.pairIsInCorrectOrder(this.rightChild(currentIndex), this.leftChild(currentIndex))
      ) {
        nextIndex = this.getRightChildIndex(currentIndex);
      } else{ nextIndex = this.getLeftChildIndex(currentIndex); } // If the node size relationship is correct, it means that node swap is not necessary, directly exit, otherwise, recursive detection and correctionif (this.pairIsInCorrectOrder(
        this.heapContainer[currentIndex],
        this.heapContainer[nextIndex],
      )) {
        break; } this.swap(currentIndex, nextIndex); currentIndex = nextIndex; }}Copy the code

conclusion

Reference 1,2 graphics are very detailed, recommended, which can be implemented in the form of their own reorganization and optimization

Btv-melezinek. Cz /binary-heap… Btv-melezinek.

The stability of

Heap sort is a kind of unstable sorting method, for the same keywords may appear at the bottom of the keyword swap to the first situation

reference

  1. Segmentfault.com/a/119000001…
  2. www.e-learn.cn/content/qit…
  3. Five minutes to learn the algorithm
  4. Heap.js
  5. Heap Visualiser