HeapsortAlgorithms and Problem Solving

HeapSort
Heapsort is a O(nlgn) time comparison based sorting algorithm which can sort in-place (swap operations are done on the array itself) but is not stable (i.e. order of element is not maintained). I have discussed general theories behind the idea of building a generic heap data structure in a separate post.

Observe that, maxheap always contain largest element at the root. So, we can extract the largest and the root now contains the next largest and so on. So, a sorted array can be created by repeatedly removing the largest element from the heap array (the root of the heap is at position 0 of the internal array), and swapping it with the end of the heap array and shrinking the heap by one. The heap is then max “heapified” at the root to maintain the heap property. Once we have extracted top n/2 element and moved the at the end of the array the rest half is already sorted in increasing order, the result is that the whole array is sorted now. Building the heap is O(n). Then repeatedly extracting the top and “heapify” it for the top n/2 elements need O(nlgn) time. So, Overall complexity is O(nlgn). Below is the simple implementation of the above idea.

protected class HeapSort {
    public int[] heap;
    public int n;

    public HeapSort(final int[] A) {
        n = A.length;
        heap = new int[n];
        heap = A;       
    }

    public int left(final int i) {
        return 2 * i + 1;
    }

    public int right(final int i) {
        return 2 * i + 2;
    }

    public int parent(final int i) {
        return i / 2;
    }

    public void swap(final int i, final int j) {
        if (i == j) {
            return;
        }
        heap[i] = heap[i] ^ heap[j];
        heap[j] = heap[i] ^ heap[j];
        heap[i] = heap[i] ^ heap[j];
    }

    public void maxHeapify(final int i) {
        final int left = left(i);
        final int right = right(i);
        int max = i;

        if (left < n && heap[left] > heap[max]) {
            max = left;
        }
        if (right < n && heap[right] > heap[max]) {
            max = right;
        }

        if (max != i) {
            swap(i, max);
            maxHeapify(max);
        }
    }

    public void buildMaxHeap() {
        int i = n / 2;
        while (i-- > 0) {
            maxHeapify(i);
        }
    }

    public void heapSort() {
        buildMaxHeap();
        for (int i = n - 1; i >= n / 2; i--) {
            swap(0, i);
            n--;
            maxHeapify(0);
        }
    }
}