Wednesday, September 17, 2014

Heap Sort Implementation Java [Heap Sort][Java]

Heapsort is a comparison-based sorting algorithm. Heapsort is part of the selection sort family; it improves on the basic selection sort by using a logarithmic-time priority queue rather than a linear-time search. Although somewhat slower in practice on most machines than a well-implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but it is not a stable sort.

Worst case performance = O(n log n)

This video is really helpful if you want to have a good understanding of heaps and sorting using min/max heaps. 

[MIT OpenCourseWare]
http://www.youtube.com/watch?v=B7hVxCmfPtM


Code:

class Heap {

    private static int[] array;
    private static int heap_size;

    private static int leftChild(int node) {
        return (node * 2 <= heap_size) ? node * 2 : -1;
    }

    private static int rightChild(int node) {
        return (node * 2 + 1 <= heap_size) ? node * 2 + 1 : -1;
    }

    private static void constructHeap() {
        for (int i = heap_size / 2; i > 0; --i) {
            max_heapify(i);
        }
    }

    private static void max_heapify(int node) {
        int consider;
        if (leftChild(node) == rightChild(node)) {  //Missing nodes (both return -1)
            return;
        } else if (leftChild(node) == -1) {         //left node missing, consider the right one
            consider = rightChild(node);
        } else if (rightChild(node) == -1) {        //right node missing, consider the left one
            consider = leftChild(node);
        } else {                                    //both nodes present, evalute which one to consider
            consider = array[leftChild(node)] >= array[rightChild(node)] ? leftChild(node) : rightChild(node);
        }

        if (array[node] < array[consider]) {
            int temp = array[node];
            array[node] = array[consider];
            array[consider] = temp;
            max_heapify(consider);
        }
    }

    private static int extractMax() {
        if (heap_size == 0) {
            System.err.println("Error: Heap is empty!");
            return -1;
        }
        int maxValue = array[1];
        int temp = array[1];
        array[1] = array[heap_size];
        array[heap_size] = temp;
        heap_size--;
        return maxValue;
    }

    public static void heapSort(int[] array_input) {

        //array to sort
        array = array_input;
        /*
         max_heap size = array.length-1 (-1 for the 0th index that we are NOT going to consider)
         The user should not have to care about leaving the 0th index empty.
         But we can't use index 0 due to the rightChild() and leftChild() calculations for
         indexes. We need to make a copy of this array so that the new copy has size (array_input+1). 
         */
        heap_size = array.length - 1;
        constructHeap();

        for (int i = array.length - 1; i > 0; --i) {
            array[i] = extractMax();
            max_heapify(1);
        }
    }

    public static void main(String[] args) {
        int[] array = {0, 7, 5, 99, 3, 2, 1, 22, 33, 42, 1, 332, 1};
        heapSort(array);
        for (int i = 1; i < array.length; ++i) {
            System.out.print(array[i] + " ");
        }
    }
}

Output:
1 1 1 2 3 5 7 22 33 42 99 332

as expected!

This code is good to understand the working. But if you want the user to just input an array (not caring about index 0) you need to accomodate for the included 0th index.

Important points where code needs to be changed in this case:

During the calculation of leftChild and rightChild -

    private static int leftChild(int node) {
        return (node * 2 + 1 <= heap_size) ? node * 2 : -1;
    }

    private static int rightChild(int node) {
        return (node * 2 + 2 <= heap_size) ? node * 2 + 1 : -1;
    }


Modified code (full):

class Heap {

    private static int[] array;
    private static int heap_size;

    private static int leftChild(int node) {
        return (node * 2 + 1 <= heap_size) ? node * 2 : -1;
    }

    private static int rightChild(int node) {
        return (node * 2 + 2 <= heap_size) ? node * 2 + 1 : -1;
    }

    private static void constructHeap() {
        for (int i = heap_size / 2; i >= 0; --i) {
            max_heapify(i);
        }
    }

    private static void max_heapify(int node) {
        int consider;
        if (leftChild(node) == rightChild(node)) {  //Missing nodes (both return -1)
            return;
        } else if (leftChild(node) == -1) {         //left node missing, consider the right one
            consider = rightChild(node);
        } else if (rightChild(node) == -1) {        //right node missing, consider the left one
            consider = leftChild(node);
        } else {                                    //both nodes present, evalute which one to consider
            consider = array[leftChild(node)] >= array[rightChild(node)] ? leftChild(node) : rightChild(node);
        }

        if (array[node] < array[consider]) {
            int temp = array[node];
            array[node] = array[consider];
            array[consider] = temp;
            max_heapify(consider);
        }
    }

    private static int extractMax() {
        if (heap_size == -1) {
            System.err.println("Error: Heap is empty!");
            return -1;
        }
        int maxValue = array[0];
        int temp = array[0];
        array[0] = array[heap_size-1];
        array[heap_size-1] = temp;
        heap_size--;
        return maxValue;
    }

    public static void heapSort(int[] array_input) {

        array = array_input; 
        heap_size = array.length;
        constructHeap();

        for (int i = array.length-1; i >= 0; --i) {
            array[i] = extractMax();
            max_heapify(0);
        }
    }

    public static void main(String[] args) {
        int[] array = {5, 5, 4, 3, 5, 2, 1};
        heapSort(array);
        for (int i = 0; i < array.length; ++i) {
            System.out.print(array[i] + " ");
        }
    }
}

Output:

1 2 3 4 5 5 5

as expected!

No comments:

Post a Comment