Heapsort

You may want to read the previous post “heap” first.

Heapsort Algorithm

Heapsort is a in-place, not stable, worst-case nlogn sorting algorithm.

The simple implementation of heapsort is simply insert all elements into the heap and then remove the root repeatedly until the heap is empty. This is implemented in the code of post “heap” and “priority queue”.

However, this implementation consumes additional memory due of the usage of the heap/priority queue. Heapsort can actually be implemented using the input data array as the memory for building the heap. Therefore, heapsort is a in-place sorting algorithm.
The in-place version has two phases. Firstly we need to build a heap. This is done by dividing the input array as two parts, the first part contains the heapified data, and the second part contains other inputs. We loop through the input array, adds the current element to the heapified part at every iteration.

The second phase is to retrieve the element from the heap. Every time we remove the root element from the heap, the heap size is reduced by 1, so the space occupied by the last element before removal will be available for storing the removed element. (Essentially, we simply swap the first element and last element of the fully-heapifed array). We do this repeatedly until the heap is empty.

If we’re using a min binary heap, the input will be sorted into descending order as we’re repeatedly putting the smallest element from the heap to the end of the heapified part. If we want to sort the array into ascending order, we simply build a max binary heap. This is easy in code as we only need to change the value comparison from “<” to “>” or “>” to “<”.

C Implementation

Below we show an implementation of heapsort to sort a randomly generated array of integers to ascending order. The heap insert and remove functions are similar to the code in the post “heap”, except that the signs are changed to build a max binary heap instead of min binary heap.

#include <stdio.h>

#include <stdlib.h>

typedef struct heapData {

    //dummy

} heapData;

typedef struct heapNode {

    int value;

    heapData data;               //dummy

} heapNode;

void insert(heapNode aNode, heapNode* heap, int size) {

    int idx;

    heapNode tmp;

    idx = size + 1;

    heap[idx] = aNode;

    while (heap[idx].value > heap[idx/2].value && idx > 1) {         //change "<" to ">"

    tmp = heap[idx];

    heap[idx] = heap[idx/2];

    heap[idx/2] = tmp;

    idx /= 2;

    }

}

void shiftdown(heapNode* heap, int size, int idx) {

    int cidx;        //index for child

    heapNode tmp;

    for (;;) {

        cidx = idx*2;

        if (cidx > size) {

            break;   //it has no child

        }

        if (cidx < size) {

            if (heap[cidx].value < heap[cidx+1].value) {//change ">" to "<"

                ++cidx;

            }

        }

        //swap if necessary

        if (heap[cidx].value > heap[idx].value) {    //change "<" to ">"

            tmp = heap[cidx];

            heap[cidx] = heap[idx];

            heap[idx] = tmp;

            idx = cidx;

        } else {

            break;

        }

    }

}

heapNode removeMax(heapNode* heap, int size) {

    int cidx;

    heapNode rv = heap[1];

    //printf("%d:%d:%d\n", size, heap[1].value, heap[size].value);

    heap[1] = heap[size];

    --size;

    shiftdown(heap, size, 1);

    return rv;

}

int main(int argc, char **argv) {

    int n; 

    int i;

    heapNode *heap;

    n = atoi(argv[1]);

    heap = (heapNode*)malloc(sizeof(heapNode)*(n+1));

    srand(time(NULL));

    for (i = 1; i <= n; ++i) {

        heap[i].value = rand()%10000;

    }

    printf("input:\n");

    for (i = 1; i <= n; ++i) {

        printf("%d ", heap[i].value);

    }

    printf("\nheapify:\n");

    for (i = 2; i <=n ;++i) {

        insert(heap[i], heap, i-1);

    } 

    for (i = 1; i <= n; ++i) {

        printf("%d ", heap[i].value);

    }

    printf("\nsort the heapified array:\n");

    for (i = n; i > 0; --i) {

        heap[i] = removeMax(heap, i);        //use the end of the heapified part to store the removed element

    }

    for (i = 1; i <= n; ++i) {

        printf("%d ", heap[i].value);

    }

    printf("\n");

}

Sample Execution

Compile the code using the command,

gcc -o hs heapsort.c

Below is a screenshot of the sample execution,

Figure 1. Heapsort Sample Run

Run Time

Heapsort has worst-case nlogn run time, which is better than quicksort’s n^2 worst case run time. However, quicksort performs better than heapsort in practice at most cases.