C language sort method - heap sort - Moment For Technology

This article has participated in the call for good writing activities, click to view: [Back end, big front-end double track submission, 20,000 yuan prize pool waiting for you to challenge!] (juejin. Cn/post / 697868…).

A heap is a nearly complete binary tree structure that also satisfies the property of a heap: the key value or index of a child node is always smaller than (or greater than) its parent node.

The following three steps are usually required to operate on the heap:

Max Heapify: Adjusts the end child of the heap so that the child is always smaller than the parent
Create Build Max Heap: Reorder all the data in the Heap
HeapSort: a recursive operation that removes the root of the first data and makes the maximum heap adjustment.

C code implementation

void maxHeapify( int num[], int start, int end )
{
    // Create parent and child indicators
    int dad = start;
    int son = dad * 2 + 1;
    while( son <= end )  // If the child node index is in the range, the comparison is performed
    {
        if( son + 1 <= end && num[son] < num[son + 1])// Compare the size of the two child nodes and select the largest one
        {
            son++;
        }
        if( num[dad] > num[son] )	// If the parent node is larger than the child node, the adjustment is complete
        {
            return;
        }
        else		               // Otherwise, swap the parent and child content and continue the comparison between child and grandchild nodes
        {
            EXCHANGE( num[dad], num[son] )
            dad = son;
            son = dad * 2 + 1; }}}void heapSort( int num[], int count )
{
    int i;    
    for( i = count / 2 - 1; i >= 0; i-- )//1. Maximum heap adjustment initialization, I starting from the last parent node adjustment
    {
        maxHeapify( num, i, count - 1 );
    }
    for( i = count - 1; i > 0; i-- )					
    {
        EXCHANGE( num[0], num[i] )	//2. Heapsort swaps the first element with the first bit of the sorted element
        maxHeapify( num, 0, i - 1 );	//3. Create the maximum heap and readjust the parent and child nodes}}Copy the code

The code looks abstract, but it is easier to understand if you print out the process of exchanging data at runtime and analyze it with a binary tree graph. The data exchange process during the code operation is as follows:

In order to facilitate viewing, binary tree graph generation software is used here to observe the data exchange process through binary tree graph. Binary tree graphics are generated using an online generation site: mshang.ca/syntree all binary tree graphics are generated using this software.

The code starts by printing out the raw data

Array elements 0, 8, 1, 5, 4, 3, 7, 9, 2, 6 will use the formula to generate the binary tree chart on the website, the software interface is as follows:

First, the array is sorted from top to bottom and converted into a binary tree.

Formula: 0[8 [5 9[2]][4[6]] [1[3] [7]]

Generate a binary tree diagram:

After converting to a binary tree, you need to make the unordered heap the maximum heap, meaning that each heap implements a value greater than any of its children. Starting with the last heap, the values of the parent and children are compared, and if the child is greater than the parent, the swap is required.

Create the maximum heap: 6 is the last child node, so the parent node is compared from 6. If the child node is larger than the parent node, the position of the child node and the parent node needs to be swapped. As can be seen from the device tree graph, child node 6 is larger than parent node 4, so the position of the parent node of the child node needs to be changed.

Formula: 0[8 [5 9[2]][6[4]] [1[3] [7]]

Swap 6 and 4

The node before 6 is 2, and 2 is smaller than the parent node 5. Continue to look for the child node 9, which is larger than the parent node 5, so the positions of 9 and 5 are swapped.

Formula: 0[8 [9 5[2]][6[4]] [1[3] [7]]

Swap 9 and 5

The child node 7 is larger than the parent node 1, and the switch continues.

Formula: 0[8 [9 5[2]][6[4]] [7[3] [1]]

Swap 7’s and 1’s

The child node 9 is larger than the parent node 8.

Formula: 0[9 [8 5[2]][6[4]] [7[3] [1]]

Swap 9 and 8

Continue to compare other nodes

Formula: 9[0 [8 5[2]][6[4]]] [7[3] [1]]]

Swap 9’s and 0’s

Formula: 9[8 [0 5[2]][6[4]]] [7[3] [1]]]

Swap 8’s and 0’s

Formula: 9[8 [50 [2]][6[4]] [7[3] [1]]]

Swap 5 and 0

At this point, the maximum heap has been created, and the number 9 at the root node is the maximum in the array.

The order of the data printed in the code is exactly the same as the order of the data analyzed by the binary tree graph. At this point the maximum number of adjustments have been made. The next step is to start heap sorting, storing the data from the root node to the last node in order to form an ordered heap.

Heap sort (maximum heap adjustment)

First, swap the first element in the array with the previous sorted element. The first element in the array is 9, and the last element after sorting is 4. Swap 9 and 4.

Formula: 4[8 [50 [2]][6[9]] [7[3] [1]]]

Swap 9 and 4

After the exchange, the bottom position of the maximum value 9 becomes the ordered region, and then the ordered region will not participate in any comparison. Next, adjust the parent and child nodes to ensure that the parent node is larger than the child node.

Formula: 8[4 [50 [2]][6[9]] [7[3] [1]]]

Swap 8’s and 4’s

Formula: 8[6 [50 [2]][4[9]]] [7[3] [1]]]

Swap 6 and 4

At this point, the number 8 is called the root node and is the maximum value in the current unordered region. Swap 8 with 2 at the bottom region and put the current maximum value 8 into the ordered region.

Formula: 2[6 [50 [8]][4[9]] [7[3] [1]]

Swap 8’s and 2’s

At this point, the 8 has been stored in the ordered region, and it will not participate in any exchange after that. After 2 becomes the root node, you need to adjust the node again to ensure that the parent node is larger than the child node.

Formula: 7[6 [50 [8]][4[9]] [2[3] [1]]

Swap 7 and 2

Formula: 7[6 [50 [8]][4[9]] [3[2] [1]]

Swap 3 and 2

The number 7 becomes the root node and is the maximum of the unordered interval. The number of the root node needs to be moved into the ordered region.Swap root nodes 7 and 0.

Formula: 0[6 [5 7[8]][4[9]]] [3[2] [1]]

Swap 7’s and 0’s

Then adjust the node formula: 6[0 [5 7[8]][4[9]] [3[2] [1]]

Swap 6’s and 0’s

Formula: 6[5 [0 7[8]][4[9]] [3[2] [1]]]

Swap 5 and 0

At this point, 6 becomes the root node, which is the maximum of the unordered interval.

Swapping the root node with the previous digit of the ordered interval, i.e., 1 and 6, requires swapping.

Formula: 1[5 [0 7[8]][4[9]] [3[2] [6]]

Swap 6 and 1

Then adjust the node again

Formula: 5[1 [0 7[8]][4[9]] [3[2] [6]]]

Swap 5 and 1

Formula: 5[4 [0 7[8]][1[9]] [3[2] [6]]

Swap 4’s and 1’s

At this point, 5 becomes the root node, and 5 needs to be moved to the ordered queue.

Next, you need to swap root node 5 and unordered node 2

Formula: 2[4 [0 7[8]][1[9]] [3[5] [6]]]

Swap 5 and 2

Adjust the node position

Formula: 4[2 [0 7[8]][1[9]] [3[5] [6]]

Swap the 4 and the 2

At this point, 4 is the maximum in the unordered list, and 4 and 1 need to be swapped

Formula: 1[2 [0 7[8]][4[9]] [3[5] [6]]

Swap 4’s and 1’s

Adjust the node position

Formula: 9[2 [0 6[7]][3[8]]] [1[4] [5]]]

Swap 3 and 1

In this case, 3 is the maximum value in the unordered list, and the positions of 3 and 0 need to be swapped.

Formula: 0[2 [3 7[8]][4[9]] [1[5] [6]]

Swap 3’s and 0’s

Formula for adjusting node position after switching: 9[0 [2 6[7]][3[8]] [1[4] [5]]

Swap 2’s and 0’s

At this point, 2 becomes the largest value in the unordered list, and 1 is the previous value in the ordered list. Swap 2 and 1.Formula: 1[0 [3 7[8]][4[9]] [2[5] [6]]

Swap 2 and 1

Now 1 is the root node, and there’s only one number left in the unordered list. Swap 1 and 0.

Formula: 0[1 [3 7[8]][4[9]] [2[5] [6]]

Swap 1’s and 0’s

So 0 becomes the root node, and all the other numbers are in the ordered list, and there are no more numbers in the unordered list, and that means the sort is done.