Heap Sort

Heapsort can be thought of as an improved Selectionsort: it divides the input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.

Algorithm:

1. Call the buildHeap() function on the list. This builds a heap from a list in O(n) operations.
2. Swap the first element of the list with the final element. Decrease the considered range of the list by one.
3. Call heapify() on the remaining list.
4. Go to step 2 unless only 1 element remains

Solution (in java):

import java.util.Arrays;

public class HeapSort {

    private static void buildHeap(int[] arr) {
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            heapify(arr, i, arr.length - 1);
        }
    }

    private static void heapify(int[] arr, int i, int size) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int max;
        if (left <= size && arr[left] > arr[i]) {
            max = left;
        } else {
            max = i;
        }

        if (right <= size && arr[right] > arr[max]) {
            max = right;
        }
        // If max is not current node, swap it with max of left and right child
        if (max != i) {
            swap(arr, i, max);
            heapify(arr, max, size);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    private static int[] heapSort(int[] arr) {

        buildHeap(arr);
        int sizeOfHeap = arr.length - 1;
        for (int i = sizeOfHeap; i > 0; i--) {
            swap(arr, 0, i);
            sizeOfHeap = sizeOfHeap - 1;
            heapify(arr, 0, sizeOfHeap);
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {11, 5, 100, 6, 13, 25, 8};
        System.out.println(Arrays.toString(heapSort(arr)));
    }
}

output:

[5, 6, 8, 11, 13, 25, 100]

The buildHeap() operation is run once, and is O(n) in performance. The heapify() function is O(log n), and is called n times. Therefore, the performance of this algorithm is O(n + n log n) = O(n log n).