Original public number: programmer’s interview question

Heap sort

Heap sort is a sort algorithm designed by using heap data structure. The heap is a nearly complete binary tree structure, and simultaneously satisfies the properties of the heap: namely, the key value or index of the child node is always smaller than (or larger than) its parent node, and the heap sort time complexity is O(nlogn). (From Wikipedia)

What is a pile of

A heap is a special complete binary tree whose property is that any node is greater than or less than or equal to its left and right nodes. If any node is greater than or equal to its left and right nodes, the heap is called the maximum heap; Conversely, any node less than or equal to its left and right nodes is called the minimum heap.

Access to heap nodes

  • Location of the left child of parent node I (2i+1)
  • Location of the right child node of parent node I (2i+2)
  • The location of the parent of child node I (i-1)/2 is rounded down

The basic idea of heap sort

  1. Unordered heap sequence
  2. Each parent is compared to the left and right children, and the large/small children are swapped with the parent until the heap is either the smallest heap or the largest heap
  3. Swap the top of the heap with the last node in the unsorted binary tree
  4. Repeat steps (2,3) until you reach the top of the heap

Step decomposition of heap sort

Unordered sequences: {0,9,6,2,3,1,5}, sorted from largest to smallestThe figure above shows building an initial maximum heap and then swapping the values at the top and bottom of the heap.

We compare the heap (1) first. Starting from the last parent node, the value of node 2 is larger than that of child nodes 5 and 6, so no adjustment is required. The value of node 1 is larger than that of child nodes 3 and 4, and there is no need to swap. The value of node 0 is smaller than that of the left and right child nodes, and then the largest child node is taken. (2) the heap represents swapping, and the child node has swapped, so it needs to determine whether its child node is larger than it. Node 4 is larger than node 1 (because node 4 is larger than node 3, node 4 is swapped), and (3) the heap represents swapping. (4) The heap completes the maximum heap initialized. (5) The heap is swapped between the top and bottom of the heap.

The next step is to repeat the process until you reach the top of the heap, as shown below:

This is the process of the complete algorithm.

Heap sort implementation code

void myswap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

void MaxHead(int *pArrayNum, int nStart, int nEnd) {
    int nF = nStart;// Number of the current parent node
    int nS = nF * 2 + 1;// The serial number of the left child of the current parent node
    while(nS <= nEnd) {
        // Determine the maximum number of left and right child nodes
        if((nS+1 <= nEnd) && (pArrayNum[nS+1] > pArrayNum[nS])) {
            nS++;// The right node is large
        }
        // Determine the size of the parent node and child node
        if(pArrayNum[nS] > pArrayNum[nF]) {
            // The child node is larger than the parent node
            myswap(pArrayNum[nS], pArrayNum[nF]);
            // Go down
            nF = nS;
            nS = nF * 2 + 1;
        }
        else {
            // The parent node is larger than the child node
            return; }}}void HeapSort(int *pArrayNum, int nCount) {
    // Initialize to build the maximum heap
    for(int i=nCount/2- 1; i>=0; i--) {
        MaxHead(pArrayNum, i, nCount- 1);
    }
    // Swap the top of the heap with the unsorted bottom of the heap, and then build the heap
    for (int i=nCount- 1; i>0; i--) {
        // The heap top value is interchanged with the unsorted heap bottom value
        myswap(pArrayNum[0], pArrayNum[i]);
        MaxHead(pArrayNum, 0, i- 1);// Rebuild the maximum heap}}Copy the code