Heap sort

This chapter introduces heap sorting in sorting algorithm .

Catalog
1.  Introduction to heap sorting
2.  Heap sort text description
3.  The time complexity and stability of heap sorting
4.  Heap sort implementation
4.1  Heap sort C Realization
4.2  Heap sort C++ Realization
4.3  Heap sort Java Realization

Reprint please indicate the source ： Heap sort - If the sky doesn't die - Blog Garden

---

For more sorting and algorithms, please refer to ： Data structure and algorithm series Catalog

Introduction to heap sorting

Heap sort (Heap Sort) It is a sort algorithm designed by using the data structure of heap .
therefore , Before learning heap sorting , It is necessary to understand the heap ！ If the reader is not familiar with heaps , It is recommended to know Pile up ( Suggestions can be made through Binary heap , Left leaning reactor , Slant pile , Binomial pile or Fibonacci pile And so on ), Then come to this chapter .

We know , The pile is divided into " The biggest pile " and " The smallest pile ". The maximum heap is usually used for " Ascending " Sort , The smallest heap is usually used for " Descending " Sort .
Since the maximum heap and the minimum heap are symmetrical , Just understand one of them . This article will explain in detail the ascending sort of the maximum heap implementation .

The basic idea of ascending sorting the largest heap ：
① Initializing the heap ： Will be in series a[1...n] Construct into maximum heap .
② Exchange data ： take a[1] and a[n] In exchange for , send a[n] yes a[1...n] Maximum of ; And then a[1...n-1] Readjust to maximum heap size . next , take a[1] and a[n-1] In exchange for , send a[n-1] yes a[1...n-1] Maximum of ; And then a[1...n-2] Readjust to maximum . By analogy , Until the whole sequence is orderly .

below , Through graphics and text to analyze the implementation process of heap sorting . Note that... Is used in the implementation " The nature of binary heap realized by array ".
The index of the first element is 0 In the case of ：
Property one ： The index for i The left child's index is (2*i+1);
Property two ： The index for i The left child's index is (2*i+2);
Property three ： The index for i The index of the parent node of is floor((i-1)/2);

for example , For the largest pile {110,100,90,40,80,20,60,10,30,50,70} for ： The index for 0 All the left child has is 1; The index for 0 My right child is 2; The index for 8 The parent of is 3.

Heap sort text description

Heap sort ( Ascending ) Code

/* 
 * ( Maximum ) Heap down adjustment algorithm 
 *
 *  notes ： In the heap of array implementation , The first N The index value of the left child of nodes is (2N+1), The child's index is right (2N+2).
 *      among ,N Index values for array subscripts , Such as... In the array 1 The number corresponds to N by 0.
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     start --  The starting position of the downregulated node ( It's usually 0, Says from the first 1 Start )
 *     end   --  Up to range ( Generally, it is the index of the last element in the array )
 */
void maxheap_down(int a[], int start, int end)
{
    int c = start;            //  At present (current) Location of nodes 
    int l = 2*c + 1;        //  Left (left) The child's position 
    int tmp = a[c];            //  At present (current) The size of the node 
    for (; l <= end; c=l,l=2*l+1)
    {
        // "l" The left child. ,"l+1" It's the right child 
        if ( l < end && a[l] < a[l+1])
            l++;        //  Choose the older of the left and right children , namely m_heap[l+1]
        if (tmp >= a[l])
            break;        //  Adjust the end 
        else            //  Exchange value 
        {
            a[c] = a[l];
            a[l]= tmp;
        }
    }
}

/*
 *  Heap sort ( From small to large )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void heap_sort_asc(int a[], int n)
{
    int i;

    //  from (n/2-1) --> 0 Successive traversal . After traversing , The resulting array is actually a ( Maximum ) Binary heap .
    for (i = n / 2 - 1; i >= 0; i--)
        maxheap_down(a, i, n-1);

    //  Adjust the sequence from the last element , Keep narrowing the scope of adjustment until the first element 
    for (i = n - 1; i > 0; i--)
    {
        //  In exchange for a[0] and a[i]. After exchanging ,a[i] yes a[0...i] The largest of .
        swap(a[0], a[i]);
        //  adjustment a[0...i-1], bring a[0...i-1] Still the largest heap .
        //  namely , Guarantee a[i-1] yes a[0...i-1] Maximum of .
        maxheap_down(a, 0, i-1);
    }
}

heap_sort_asc(a, n) The role of is ： An array a Sort in ascending order ; among ,a It's an array ,n It's array length .
heap_sort_asc(a, n) The operation of is divided into two parts ： Initializing the heap and Exchange data .
maxheap_down(a, start, end) Is the downward adjustment algorithm of the maximum heap .

The following demonstration heap_sort_asc(a, n) Yes a={20,30,90,40,70,110,60,10,100,50,80}, n=11 Perform the heap sort process . Here's the array a Corresponding initialization structure ：

1 Initializing the heap

In the heap sorting algorithm , First, convert the array to be sorted into a binary heap .
Here's an example of an array {20,30,90,40,70,110,60,10,100,50,80} Convert to maximum heap {110,100,90,40,80,20,60,10,30,50,70} Steps for .

1.1 i=11/2-1, namely i=4

It's on it maxheap_down(a, 4, 9) Adjustment process .maxheap_down(a, 4, 9) The role of the a[4...9] Down regulation ;a[4] My left child is a[9], The right child is a[10]. When adjusting , Choose the older of the left and right children ( namely a[10]) and a[4] In exchange for .

1.2 i=3

It's on it maxheap_down(a, 3, 9) Adjustment process .maxheap_down(a, 3, 9) The role of the a[3...9] Down regulation ;a[3] My left child is a[7], The right child is a[8]. When adjusting , Choose the older of the left and right children ( namely a[8]) and a[4] In exchange for .

1.3 i=2

It's on it maxheap_down(a, 2, 9) Adjustment process .maxheap_down(a, 2, 9) The role of the a[2...9] Down regulation ;a[2] My left child is a[5], The right child is a[6]. When adjusting , Choose the older of the left and right children ( namely a[5]) and a[2] In exchange for .

1.4 i=1

It's on it maxheap_down(a, 1, 9) Adjustment process .maxheap_down(a, 1, 9) The role of the a[1...9] Down regulation ;a[1] My left child is a[3], The right child is a[4]. When adjusting , Choose the older of the left and right children ( namely a[3]) and a[1] In exchange for . After the exchange ,a[3] by 30, It's better than its right child a[8] Be big , next , Then exchange them .

1.5 i=0

It's on it maxheap_down(a, 0, 9) Adjustment process .maxheap_down(a, 0, 9) The role of the a[0...9] Down regulation ;a[0] My left child is a[1], The right child is a[2]. When adjusting , Choose the older of the left and right children ( namely a[2]) and a[0] In exchange for . After the exchange ,a[2] by 20, It's bigger than its left and right children , Choose older children ( That is, the left child ) and a[2] In exchange for .

Adjustment complete , You get the maximum heap . here , Array {20,30,90,40,70,110,60,10,100,50,80} It becomes {110,100,90,40,80,20,60,10,30,50,70}.

The first 2 part Exchange data

After converting the array to the maximum heap , Then we have to exchange data , This makes the array a truly ordered array .
The data exchange part is relatively simple , The following is just a diagram of putting the maximum value at the end of the array .

It's when n=10 when , Schematic diagram of data exchange .
When n=10 when , First of all, exchange a[0] and a[10], bring a[10] yes a[0...10] Maximum value between ; then , adjustment a[0...9] Make it called the maximum heap . After the exchange ：a[10] Is ordered ！
When n=9 when , First of all, exchange a[0] and a[9], bring a[9] yes a[0...9] Maximum value between ; then , adjustment a[0...8] Make it called the maximum heap . After the exchange ：a[9...10] Is ordered ！
...
And so on , until a[0...10] Is ordered .

The time complexity and stability of heap sorting

Heap sort time complexity
The time complexity of heap sorting is O(N*lgN).
Let's assume that the sequence being sorted has N Number . The time complexity of traversing a trip is O(N), How many times does it take to traverse ？
Heap sorting is based on binary heap , A binary pile is a binary tree , The number of times it needs to traverse is the depth of the binary tree , And according to the definition of complete binary tree , Its depth is at least lg(N+1). What's the maximum ？ Because the binary heap is a complete binary tree , therefore , It's no deeper than lg(2N). therefore , The time complexity of traversing a trip is O(N), The number of traversals is between lg(N+1) and lg(2N) Between ; Therefore, the time complexity is O(N*lgN).

Heap sort stability
Heap sorting is an unstable algorithm , It doesn't meet the definition of stable algorithm . When it exchanges data , Is to compare the data between the parent node and the child node , therefore , Even if there are two sibling nodes with equal values , Their relative order may also change in order .
Algorithm stability -- Let's assume that there exists in a sequence a[i]=a[j], If before sorting ,a[i] stay a[j] front ; And after sorting ,a[i] Still in a[j] front . Then the sorting algorithm is stable ！

Heap sort implementation

Here are three implementations of heap sorting ：C、C++ and Java. The principle and output results of these three implementations are the same , Each implementation includes " The ascending order corresponding to the largest heap " and " The descending sort corresponding to the smallest heap ".
Heap sort C Realization
Implementation code (heap_sort.c)

/**
 *  Heap sort ：C  Language 
 *
 * @author skywang
 * @date 2014/03/12
 */

#include <stdio.h>

//  The length of the array 
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
#define swap(a,b) (a^=b,b^=a,a^=b)

/*
 * ( Maximum ) Heap down adjustment algorithm 
 *
 *  notes ： In the heap of array implementation , The first N The index value of the left child of nodes is (2N+1), The child's index is right (2N+2).
 *      among ,N Index values for array subscripts , Such as... In the array 1 The number corresponds to N by 0.
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     start --  The starting position of the downregulated node ( It's usually 0, Says from the first 1 Start )
 *     end   --  Up to range ( Generally, it is the index of the last element in the array )
 */
void maxheap_down(int a[], int start, int end)
{
    int c = start;            //  At present (current) Location of nodes 
    int l = 2*c + 1;        //  Left (left) The child's position 
    int tmp = a[c];            //  At present (current) The size of the node 
    for (; l <= end; c=l,l=2*l+1)
    {
        // "l" The left child. ,"l+1" It's the right child 
        if ( l < end && a[l] < a[l+1])
            l++;        //  Choose the older of the left and right children , namely m_heap[l+1]
        if (tmp >= a[l])
            break;        //  Adjust the end 
        else            //  Exchange value 
        {
            a[c] = a[l];
            a[l]= tmp;
        }
    }
}

/*
 *  Heap sort ( From small to large )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void heap_sort_asc(int a[], int n)
{
    int i;

    //  from (n/2-1) --> 0 Successive traversal . After traversing , The resulting array is actually a ( Maximum ) Binary heap .
    for (i = n / 2 - 1; i >= 0; i--)
        maxheap_down(a, i, n-1);

    //  Adjust the sequence from the last element , Keep narrowing the scope of adjustment until the first element 
    for (i = n - 1; i > 0; i--)
    {
        //  In exchange for a[0] and a[i]. After exchanging ,a[i] yes a[0...i] The largest of .
        swap(a[0], a[i]);
        //  adjustment a[0...i-1], bring a[0...i-1] Still the largest heap .
        //  namely , Guarantee a[i-1] yes a[0...i-1] Maximum of .
        maxheap_down(a, 0, i-1);
    }
}

/*
 * ( Minimum ) Heap down adjustment algorithm 
 *
 *  notes ： In the heap of array implementation , The first N The index value of the left child of nodes is (2N+1), The child's index is right (2N+2).
 *      among ,N Index values for array subscripts , Such as... In the array 1 The number corresponds to N by 0.
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     start --  The starting position of the downregulated node ( It's usually 0, Says from the first 1 Start )
 *     end   --  Up to range ( Generally, it is the index of the last element in the array )
 */
void minheap_down(int a[], int start, int end)
{
    int c = start;            //  At present (current) Location of nodes 
    int l = 2*c + 1;        //  Left (left) The child's position 
    int tmp = a[c];            //  At present (current) The size of the node 
    for (; l <= end; c=l,l=2*l+1)
    {
        // "l" The left child. ,"l+1" It's the right child 
        if ( l < end && a[l] > a[l+1])
            l++;        //  Choose the smaller of the left and right children 
        if (tmp <= a[l])
            break;        //  Adjust the end 
        else            //  Exchange value 
        {
            a[c] = a[l];
            a[l]= tmp;
        }
    }
}

/*
 *  Heap sort ( From big to small )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void heap_sort_desc(int a[], int n)
{
    int i;

    //  from (n/2-1) --> 0 Go through each... Step by step . After traversing , The resulting array is actually a minimum heap .
    for (i = n / 2 - 1; i >= 0; i--)
        minheap_down(a, i, n-1);

    //  Adjust the sequence from the last element , Keep narrowing the scope of adjustment until the first element 
    for (i = n - 1; i > 0; i--)
    {
        //  In exchange for a[0] and a[i]. After exchanging ,a[i] yes a[0...i] The smallest of all .
        swap(a[0], a[i]);
        //  adjustment a[0...i-1], bring a[0...i-1] It's still the smallest heap .
        //  namely , Guarantee a[i-1] yes a[0...i-1] Minimum of .
        minheap_down(a, 0, i-1);
    }
}

void main()
{
    int i;
    int a[] = {20,30,90,40,70,110,60,10,100,50,80};
    int ilen = LENGTH(a);

    printf("before sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");

    heap_sort_asc(a, ilen);            //  Ascending order 
    //heap_sort_desc(a, ilen);        //  Descending order 

    printf("after  sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");
}

Heap sort C++ Realization
Implementation code (HeapSort.cpp)

/**
 *  Heap sort ：C++
 *
 * @author skywang
 * @date 2014/03/11
 */

#include <iostream>
using namespace std;

/*
 * ( Maximum ) Heap down adjustment algorithm 
 *
 *  notes ： In the heap of array implementation , The first N The index value of the left child of nodes is (2N+1), The child's index is right (2N+2).
 *      among ,N Index values for array subscripts , Such as... In the array 1 The number corresponds to N by 0.
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     start --  The starting position of the downregulated node ( It's usually 0, Says from the first 1 Start )
 *     end   --  Up to range ( Generally, it is the index of the last element in the array )
 */
void maxHeapDown(int* a, int start, int end)
{
    int c = start;            //  At present (current) Location of nodes 
    int l = 2*c + 1;        //  Left (left) The child's position 
    int tmp = a[c];            //  At present (current) The size of the node 
    for (; l <= end; c=l,l=2*l+1)
    {
        // "l" The left child. ,"l+1" It's the right child 
        if ( l < end && a[l] < a[l+1])
            l++;        //  Choose the older of the left and right children , namely m_heap[l+1]
        if (tmp >= a[l])
            break;        //  Adjust the end 
        else            //  Exchange value 
        {
            a[c] = a[l];
            a[l]= tmp;
        }
    }
}

/*
 *  Heap sort ( From small to large )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void heapSortAsc(int* a, int n)
{
    int i,tmp;

    //  from (n/2-1) --> 0 Successive traversal . After traversing , The resulting array is actually a ( Maximum ) Binary heap .
    for (i = n / 2 - 1; i >= 0; i--)
        maxHeapDown(a, i, n-1);

    //  Adjust the sequence from the last element , Keep narrowing the scope of adjustment until the first element 
    for (i = n - 1; i > 0; i--)
    {
        //  In exchange for a[0] and a[i]. After exchanging ,a[i] yes a[0...i] The largest of .
        tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        //  adjustment a[0...i-1], bring a[0...i-1] Still the largest heap .
        //  namely , Guarantee a[i-1] yes a[0...i-1] Maximum of .
        maxHeapDown(a, 0, i-1);
    }
}

/*
 * ( Minimum ) Heap down adjustment algorithm 
 *
 *  notes ： In the heap of array implementation , The first N The index value of the left child of nodes is (2N+1), The child's index is right (2N+2).
 *      among ,N Index values for array subscripts , Such as... In the array 1 The number corresponds to N by 0.
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     start --  The starting position of the downregulated node ( It's usually 0, Says from the first 1 Start )
 *     end   --  Up to range ( Generally, it is the index of the last element in the array )
 */
void minHeapDown(int* a, int start, int end)
{
    int c = start;            //  At present (current) Location of nodes 
    int l = 2*c + 1;        //  Left (left) The child's position 
    int tmp = a[c];            //  At present (current) The size of the node 
    for (; l <= end; c=l,l=2*l+1)
    {
        // "l" The left child. ,"l+1" It's the right child 
        if ( l < end && a[l] > a[l+1])
            l++;        //  Choose the smaller of the left and right children 
        if (tmp <= a[l])
            break;        //  Adjust the end 
        else            //  Exchange value 
        {
            a[c] = a[l];
            a[l]= tmp;
        }
    }
}

/*
 *  Heap sort ( From big to small )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     n --  Length of array 
 */
void heapSortDesc(int* a, int n)
{
    int i,tmp;

    //  from (n/2-1) --> 0 Go through each... Step by step . After traversing , The resulting array is actually a minimum heap .
    for (i = n / 2 - 1; i >= 0; i--)
        minHeapDown(a, i, n-1);

    //  Adjust the sequence from the last element , Keep narrowing the scope of adjustment until the first element 
    for (i = n - 1; i > 0; i--)
    {
        //  In exchange for a[0] and a[i]. After exchanging ,a[i] yes a[0...i] The smallest of all .
        tmp = a[0];
        a[0] = a[i];
        a[i] = tmp;
        //  adjustment a[0...i-1], bring a[0...i-1] It's still the smallest heap .
        //  namely , Guarantee a[i-1] yes a[0...i-1] Minimum of .
        minHeapDown(a, 0, i-1);
    }
}

int main()
{
    int i;
    int a[] = {20,30,90,40,70,110,60,10,100,50,80};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    heapSortAsc(a, ilen);            //  Ascending order 
    //heapSortDesc(a, ilen);        //  Descending order 

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

Heap sort Java Realization
Implementation code (HeapSort.java)

/**
 *  Heap sort ：Java
 *
 * @author skywang
 * @date 2014/03/11
 */

public class HeapSort {

    /*
     * ( Maximum ) Heap down adjustment algorithm 
     *
     *  notes ： In the heap of array implementation , The first N The index value of the left child of nodes is (2N+1), The child's index is right (2N+2).
     *      among ,N Index values for array subscripts , Such as... In the array 1 The number corresponds to N by 0.
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     start --  The starting position of the downregulated node ( It's usually 0, Says from the first 1 Start )
     *     end   --  Up to range ( Generally, it is the index of the last element in the array )
     */
    public static void maxHeapDown(int[] a, int start, int end) {
        int c = start;            //  At present (current) Location of nodes 
        int l = 2*c + 1;        //  Left (left) The child's position 
        int tmp = a[c];            //  At present (current) The size of the node 

        for (; l <= end; c=l,l=2*l+1) {
            // "l" The left child. ,"l+1" It's the right child 
            if ( l < end && a[l] < a[l+1])
                l++;        //  Choose the older of the left and right children , namely m_heap[l+1]
            if (tmp >= a[l])
                break;        //  Adjust the end 
            else {            //  Exchange value 
                a[c] = a[l];
                a[l]= tmp;
            }
        }
    }

    /*
     *  Heap sort ( From small to large )
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     n --  Length of array 
     */
    public static void heapSortAsc(int[] a, int n) {
        int i,tmp;

        //  from (n/2-1) --> 0 Successive traversal . After traversing , The resulting array is actually a ( Maximum ) Binary heap .
        for (i = n / 2 - 1; i >= 0; i--)
            maxHeapDown(a, i, n-1);

        //  Adjust the sequence from the last element , Keep narrowing the scope of adjustment until the first element 
        for (i = n - 1; i > 0; i--) {
            //  In exchange for a[0] and a[i]. After exchanging ,a[i] yes a[0...i] The largest of .
            tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            //  adjustment a[0...i-1], bring a[0...i-1] Still the largest heap .
            //  namely , Guarantee a[i-1] yes a[0...i-1] Maximum of .
            maxHeapDown(a, 0, i-1);
        }
    }

    /*
     * ( Minimum ) Heap down adjustment algorithm 
     *
     *  notes ： In the heap of array implementation , The first N The index value of the left child of nodes is (2N+1), The child's index is right (2N+2).
     *      among ,N Index values for array subscripts , Such as... In the array 1 The number corresponds to N by 0.
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     start --  The starting position of the downregulated node ( It's usually 0, Says from the first 1 Start )
     *     end   --  Up to range ( Generally, it is the index of the last element in the array )
     */
    public static void minHeapDown(int[] a, int start, int end) {
        int c = start;            //  At present (current) Location of nodes 
        int l = 2*c + 1;        //  Left (left) The child's position 
        int tmp = a[c];            //  At present (current) The size of the node 

        for (; l <= end; c=l,l=2*l+1) {
            // "l" The left child. ,"l+1" It's the right child 
            if ( l < end && a[l] > a[l+1])
                l++;        //  Choose the smaller of the left and right children 
            if (tmp <= a[l])
                break;        //  Adjust the end 
            else {            //  Exchange value 
                a[c] = a[l];
                a[l]= tmp;
            }
        }
    }

    /*
     *  Heap sort ( From big to small )
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     n --  Length of array 
     */
    public static void heapSortDesc(int[] a, int n) {
        int i,tmp;

        //  from (n/2-1) --> 0 Go through each... Step by step . After traversing , The resulting array is actually a minimum heap .
        for (i = n / 2 - 1; i >= 0; i--)
            minHeapDown(a, i, n-1);

        //  Adjust the sequence from the last element , Keep narrowing the scope of adjustment until the first element 
        for (i = n - 1; i > 0; i--) {
            //  In exchange for a[0] and a[i]. After exchanging ,a[i] yes a[0...i] The smallest of all .
            tmp = a[0];
            a[0] = a[i];
            a[i] = tmp;
            //  adjustment a[0...i-1], bring a[0...i-1] It's still the smallest heap .
            //  namely , Guarantee a[i-1] yes a[0...i-1] Minimum of .
            minHeapDown(a, 0, i-1);
        }
    }

    public static void main(String[] args) {
        int i;
        int a[] = {20,30,90,40,70,110,60,10,100,50,80};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        heapSortAsc(a, a.length);            //  Ascending order 
        //heapSortDesc(a, a.length);        //  Descending order 

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }
}

Their output ：

before sort:20 30 90 40 70 110 60 10 100 50 80 
after  sort:10 20 30 40 50 60 70 80 90 100 110