Implementation of Heap Sort

Question

Is this the correct implementation of Heap Sort using Java? How can it be improved further?

import java.util.Arrays;

public class HeapSort {

    public static int heapSize;
    public static int LEFT(int i)
    {
        //returns left index of a zero index based array
        return 2*i+1;
    }

    public static int RIGHT(int i)
    {
        //returns right index of a zero based array
        return 2*i+2;
    }


    public static void BUILD_MAX_HEAP(int A[])
    {
        heapSize = A.length;//heap size initialised
        for(int i=A.length/2; i>=0;i--)//since n/2, n/2+1 ... are leaves we can start from n/2 step downwards
        {
            //call MAX_HEAPIFY on each root node starting from n/2
            MAX_HEAPIFY(A, i);
        }
    }


    public static void MAX_HEAPIFY(int A[],int i)
    {
        int l=LEFT(i);//the left element's index which is 2*i+1 (for zero based indexed array)
        int r=RIGHT(i);//right index = 2*i+2;
        int largestElementIndex = -1;//index can't be negative so initialise largest index , it will be used later
        //heapSize is the current size of the heap being worked upon
        //check if left index lies within the heap.
        //if element at left index is greater than root(A[i]) element, max heap property is violated
        //copy the index of violated element in largestElementIndex
        if(l<heapSize && A[l]>A[i]){
            largestElementIndex = l;
        }
        else //if max heap property is not violated copy the root's index in largestElementIndex
        {
            largestElementIndex=i;
        }
        //check to see the right sub tree for max heap property violation
        //here the largestElementIndex is calculated from previous step
        if(r<heapSize && A[r]>A[largestElementIndex])
        {
            largestElementIndex = r;
        }
        //if root doesn't has the largest index then swap the largest element with root element

        if(largestElementIndex!=i)
        {
            int temp = A[i];
            A[i]=A[largestElementIndex];
            A[largestElementIndex]=temp;
            //after swap, recursively call the MAX_HEAPIFY on the largest index(root element)
            MAX_HEAPIFY(A, largestElementIndex);
        }
    }

    public static void HEAP_SORT(int A[])
    {
        //max heap is built with heapSize initialised
        BUILD_MAX_HEAP(A);
        //starting from end loop through entire array
        for(int i=A.length-1;i>=0;i--)
        {
            //since heap is already heapified and maintains max heap property
            //the first element of the array is root of max heap
            //swap it with the extreme element of the array i.e. setting the largest element to the end of array
            int temp = A[0];
            A[0]=A[i];
            A[i]=temp;
            //reduce the heap window by 1
            heapSize  = heapSize-1;
            //call max heapify on the reduced heap
            MAX_HEAPIFY(A,0);
        }
    }

    public static void main(String[] args) {


        int A[] = new int[]{4,1,3,2,16,9,10,14,8,7};
        HEAP_SORT(A);
        System.out.println(Arrays.toString(A));
    }
}

Answer 1

As everyone has immediately pointed out, please stick with the namingConventions for methods and parameter names.

Your code is not object oriented, as Java code should be. One sign is that you are using static functions everywhere. Another hint is that the name of a class should always be a noun; if it's a verb then your objects are likely to be crappy. You want to define a MaxHeap class. Its outline should look like this:

public class MaxHeap {
    private int data[];
    private int size;

    public static void sort(int data[]) { ... }

    public MaxHeap(int data[]) { ... }
    public int removeNext() { ... }
    public int size() { return this.size; }

    private int leftChild(int i) { return 2 * i + 1; }
    private int rightChild(int i) { return 2 * i + 2; }
    private void heapify(int i) { ... }
}

Decide what operations you want to publicly support in your interface. You'll need the constructor. Since you will be doing removal of the root node in your HEAD_SORT() function anyway, you might as well support that in the public interface as removeNext(). A size() method is trivial to implement. It would be nice to implement add(int datum) as well, but for now let's leave it out since it's not necessary for your immediate goal of implementing heapsort. We should also provide sort(int[] data) as a class method, because that is the point of this exercise. (There's no need to call it heapSort(int[] data), as "heap" is already part of the name of the class.) Everything else should be declared private — the inner workings of the class are nobody else's business.

The heap constructor is just your BUILD_MAX_HEAP() code. The only real correction I would make is that you can start i one element before where you did.

public MaxHeap(int data[]) {
    this.data = data;
    this.size = data.length;
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(i);
    }
}

Now, on to the heapify() method. There's no need to call it maxHeapify(), since it's a member of the MaxHeap class. It can just take one parameter, since the data array is now an instance variable. Also,

private void heapify(int i) {
    // You might as well start with this optimistic assumption
    int largestElementIndex = i;

    // The optimistic assumption leads to nice parallelism between the
    // left-child and right-child cases.
    int l = leftChild(i);
    if (l < size && data[l] > data[largestElementIndex]) {
        largestElementIndex = l;
    }
    int r = rightChild(i);
    if (r < size && data[r] > data[largestElementIndex]) {
        largestElementIndex = r;
    }

    // If heap consistency was locally violated
    if (largestElementIndex != i) {
        int swap = data[i];
        data[i] = data[largestElementIndex];
        data[largestElementIndex] = swap;

        // Recursively heapify the affected sub-tree
        heapify(largestElementIndex);
    }
}

Here's removeNext(). It returns the next largest element (the root node value) and shrinks the heap.

public int removeNext() throws NoSuchElementException {
    if (size == 0) {
        throw new NoSuchElementException();
    }
    int next = data[0];
    data[0] = data[--size];
    heapify(0);
    return next;
}

Finally, here's sort().

public static void sort(int[] data) {
    MaxHeap heap = new MaxHeap(data);
    for (int i = heap.size() - 1; i >= 0; i--) {
        int nextMax = heap.removeNext();

        // This is a rather naughty move, since heap.data is
        // aliased to data.  We do this only because we know
        // from the way the heap works that the end of the array
        // can be used to store our sorted result in place.
        data[i] = nextMax;
    }
}

---

One thing I'm not happy about in the above code is the fact that the MaxHeap adopts the input array rather than making a copy. That is probably surprising behaviour to users of the class, who probably don't expect the contents of the passed-in data array to be modified.

On the other hand, it's nice to be able to implement sort() in place without allocating another array.

One cop-out would be to make the constructor private, essentially declaring that the code in this class is only usable through the sort() function.

A workaround is to implement two variants of the constructor, such that you have to explicitly ask for the array to be adopted:

/**
 * Copies the data
 */
public MaxHeap(int data[]) {
    this(data, true);
}

/**
 * If copyData is false, MaxHeap adopts the data array, and may overwrite its
 * contents; it does not make a copy!
 */
public MaxHeap(int data[], boolean copyData) {
    this.data = copyData ? Arrays.copyOf(data, data.length) : data;
    ...
}

public static void sort(int[] data) {
    MaxHeap heap = new MaxHeap(data, false);
    ...
}