current position:Home>JavaScript algorithm -- heap sorting

JavaScript algorithm -- heap sorting

2022-04-29 18:27:38Zhuge Hanxin

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 :
 Insert picture description here
Small pile top :
 Insert picture description here

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 .

3、 ... and 、 Dynamic diagram demonstration

Moving graph 1:
https://oscimg.oschina.net/oscnet/849589-20171015231308699-356134237.gif
Moving graph 2:
 Insert picture description here

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 .
 Insert picture description here
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 .

 Insert picture description here
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 !
 Insert picture description here
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 ).
 Insert picture description here
 Insert picture description here
step 3
Next, repeat step 2, Until the number of elements in the heap is 1:
 Insert picture description here
 Insert picture description here
 Insert picture description here

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

reference :

Ten classic sorting algorithm animations , Just look at me !
JS Implement heap sort
js Heap sort algorithm
Javascript Algorithm —— Heap sort

copyright notice
author[Zhuge Hanxin],Please bring the original link to reprint, thank you.
https://en.qdmana.com/2022/119/202204291657165200.html

Random recommended