Heap Sort

Properties

• Not stable
• O(1) extra space (see discussion)
• O(n·lg(n)) time
• Not really adaptive

Discussion

Heap sort is simple to implement, performs an O(n·lg(n)) in-place sort, but is not stable.

The first loop, the Θ(n) "heapify" phase, puts the array into heap order. The second loop, the O(n·lg(n)) "sortdown" phase, repeatedly extracts the maximum and restores heap order.

The sink function is written recursively for clarity. Thus, as shown, the code requires Θ(lg(n)) space for the recursive call stack. However, the tail recursion in sink() is easily converted to iteration, which yields the O(1) space bound.

Both phases are slightly adaptive, though not in any particularly useful manner. In the nearly sorted case, the heapify phase destroys the original order. In the reversed case, the heapify phase is as fast as possible since the array starts in heap order, but then the sortdown phase is typical. In the few unique keys case, there is some speedup but not as much as in shell sort or 3-way quicksort.

Program C Code

// C implementation of Heap Sort

#include <stdio.h>

#include <stdlib.h>

// A heap has current size and array of elements

struct MaxHeap

{

    int size;

    int* array;

};

// A utility function to swap to integers

void swap(int* a, int* b) { int t = *a; *a = *b;  *b = t; }

// The main function to heapify a Max Heap. The function

// assumes that everything under given root (element at

// index idx) is already heapified

void maxHeapify(struct MaxHeap* maxHeap, int idx)

{

    int largest = idx;  // Initialize largest as root

    int left = (idx << 1) + 1;  // left = 2*idx + 1

    int right = (idx + 1) << 1; // right = 2*idx + 2

    // See if left child of root exists and is greater than

    // root

    if (left < maxHeap->size &&

        maxHeap->array[left] > maxHeap->array[largest])

        largest = left;

    // See if right child of root exists and is greater than

    // the largest so far

    if (right < maxHeap->size &&

        maxHeap->array[right] > maxHeap->array[largest])

        largest = right;

    // Change root, if needed

    if (largest != idx)

    {

        swap(&maxHeap->array[largest], &maxHeap->array[idx]);

        maxHeapify(maxHeap, largest);

    }

}

// A utility function to create a max heap of given capacity

struct MaxHeap* createAndBuildHeap(int *array, int size)

{

    int i;

    struct MaxHeap* maxHeap =

              (struct MaxHeap*) malloc(sizeof(struct MaxHeap));

    maxHeap->size = size;   // initialize size of heap

    maxHeap->array = array; // Assign address of first element of array

    // Start from bottommost and rightmost internal mode and heapify all

    // internal modes in bottom up way

    for (i = (maxHeap->size - 2) / 2; i >= 0; --i)

        maxHeapify(maxHeap, i);

    return maxHeap;

}

// The main function to sort an array of given size

void heapSort(int* array, int size)

{

    // Build a heap from the input data.

    struct MaxHeap* maxHeap = createAndBuildHeap(array, size);

    // Repeat following steps while heap size is greater than 1.

    // The last element in max heap will be the minimum element

    while (maxHeap->size > 1)

    {

        // The largest item in Heap is stored at the root. Replace

        // it with the last item of the heap followed by reducing the

        // size of heap by 1.

        swap(&maxHeap->array[0], &maxHeap->array[maxHeap->size - 1]);

        --maxHeap->size;  // Reduce heap size

        // Finally, heapify the root of tree.

        maxHeapify(maxHeap, 0);

    }

}

// A utility function to print a given array of given size

void printArray(int* arr, int size)

{

    int i;

    for (i = 0; i < size; ++i)

        printf("%d ", arr[i]);

}

/* Driver program to test above functions */

int main()

{

    int arr[] = {12, 11, 13, 5, 6, 7};

    int size = sizeof(arr)/sizeof(arr[0]);

    printf("Given array is \n");

    printArray(arr, size);

    heapSort(arr, size);

    printf("\nSorted array is \n");

    printArray(arr, size);

    return 0;

}