# JavaScript algorithm -- heap sorting

2022-04-29 18:27:38

## One 、 Knowledge preparation

** The first is the concept of heap .** The pile here can be simply understood as a pyramid shaped image . We use binary trees to construct , But our binary tree is complete , That is, the expansion of the tree should be arranged in order .

• The heap is a complete binary tree .
• Perfect binary tree ： Binary tree except the last layer , The number of other stratification points reaches the maximum , All nodes of the last layer are concentrated on the left （ When the left nodes are full , The node can only be missing on the right ）.
• Big pile top ： The root node is the maximum , The value of each node is greater than or equal to the value of its child node .
• Small cap pile ： The root node is the minimum , The value of each node is less than or equal to the value of its child node .
• Heap storage ： The heap is implemented by an array , It is equivalent to traversing the binary tree .

Pile top ：

Small pile top ：

## Two 、 Sorting ideas

• Convert the initial binary tree into a large top heap （heapify）（ The essence is to start from the first non leaf node , From bottom to top , right to left , Do... For each non leaf node heapify operation ）, At this time, the root node is the maximum , Exchange it with the last node .
• Except for the last node , Convert the new heap composed of other nodes into a large top heap （ In essence, it is to do... On the root node heapify operation ）, At this time, the root node is the next maximum , Exchange it with the last node .
• Repeat step 2, Until the number of elements in the heap is 1（ Or the length of its corresponding array is 1）, Sort complete .

Moving graph 1：

Moving graph 2：

## Four 、JS Code implementation

``````**//  Swap two nodes
function swap(A, i, j) {
let temp = A[i];
A[i] = A[j];
A[j] = temp;
}

//  take  i  The pile below the node is sorted into a large top pile , Note that the foundation of this step is actually ：
//  hypothesis   node  i  The following sub pile is already a large top pile ,shiftDown Functionally implemented
//  The function is actually ： find   node  i  In the include node  i  The right position in the pile . Back
//  Will write a  for  loop , Start with the first non leaf node , For every non leaf node
//  All implemented  shiftDown operation , So it satisfies the node  i  The following sub heap is already a big one
// Top pile
function shiftDown(A, i, length) {
let temp = A[i]; //  Current parent node
// j<length  The purpose of is to  i  The following nodes are all adjusted in order
for(let j = 2*i+1; j < length; j = 2*j+1) {
temp = A[i];  //  take  A[i]  Take out , The whole process is equivalent to finding  A[i]  Where to be
if(j+1 < length && A[j] < A[j+1]) {
j++;   //  Find the older of the two children , Compare it with the parent node
}
if(temp < A[j]) {
swap(A, i, j) //  If the parent is smaller than the child : In exchange for ; Otherwise jump out
i = j;  //  After exchanging ,temp  The subscript of becomes  j
} else {
break;
}
}
}

//  Heap sort
function heapSort(A) {
//  Initializing the big top heap , Start with the first non leaf node
for(let i = Math.floor(A.length/2-1); i >= 0; i--) {
shiftDown(A, i, A.length);
}
//  Sort , every time for Loop to find a current maximum , Array length minus one
for(let i = Math.floor(A.length-1); i > 0; i--) {
swap(A, 0, i); //  The root node exchanges with the last node
shiftDown(A, 0, i); //  Adjust from root , And the last node is already when
//  Front maximum , There's no need to compare , So the third parameter
//  by  i, That is, to compare to the previous node of the last node
}
}

let Arr = [3, 6, 13, 8, 2];
heapSort(Arr);
console.log(Arr); // [2, 3, 6, 8, 13]

``````

The code looks complex . In fact, we only need to remember two points ：
1、 The array facing the heap sort is unordered at first , This is the time , We need to build a sort top in the rule （ The maximum or minimum of all ）; So that's the first loop you need to do in the code , as follows ：

`````` //  Initializing the big top heap , Start with the first non leaf node
for(let i = Math.floor(A.length/2-1); i >= 0; i--) {
shiftDown(A, i, A.length);
}
``````

Cycle completion , We can get the following data ：

``````[13, 8, 3, 6, 2]
``````

The number above is the data after the first time of our cycle , You can know , Put them into the whole binary tree in turn , The parent node is always the largest one .
Then we just need to continue the cycle .

2、 Through the first cycle , The whole complete binary tree has been constructed , But the data has not been sorted yet , All we need to do is put this binary tree , Repeat method 1 , Sort . That's why there's a second cycle , as follows ：

`````` //  Sort , every time for Loop to find a current maximum , Array length minus one
for(let i = Math.floor(A.length-1); i > 0; i--) {
swap(A, 0, i); //  The root node exchanges with the last node
shiftDown(A, 0, i); //  Adjust from root , And the last node is already when
//  Front maximum , There's no need to compare , So the third parameter
//  by  i, That is, to compare to the previous node of the last node
}
``````

## 5、 ... and 、 Assist in understanding the case

step 1
Initializing the big top heap , First select the last non leaf node ( We just need to adjust the size relationship between the parent node and the child node , The size relationship between leaf nodes does not need to be adjusted ). Set the array to arr, Then the subscript of the first non leaf node is ：i = Math.floor(arr.length/2 - 1) = 1, That's numbers 4, As shown in the dotted line box , Find the maximum of three numbers , Exchange with the parent node .

then , Subscript i Decrease in turn 1（ That is, start from the first non leaf node , right to left , Traverse all non leaf nodes from bottom to top ）. This is true for every subsequent adjustment ： Find the maximum value in the parent-child node , exchange .

The number in this step 6、1 After exchanging , Numbers [1,5,4] The composition of the heap is out of order , One step adjustment is needed . So pay attention to , After adjusting one non leaf node at a time , We should observe whether it will affect the sub heap order ！

After this adjustment , The root node is the maximum , Formed a large top pile , Exchange the root node with the last node .

Step two
Except for the current last node 6( That is, the maximum value ), Add the remaining nodes [4,5,3,1] Form a new reactor and convert it into a large top reactor ( observe , At this time, other nodes other than the root node , All meet the characteristics of large top pile , So you can start from the root node 4 Began to adjust , Find out 4 It should be in the right position ).

step 3
Next, repeat step 2, Until the number of elements in the heap is 1：

The number of elements in the heap is 1, Sort complete .

reference ：