Implementation of Heap Sort
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 &gt;= 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 &lt; size &amp;&amp; data[l] &gt; data[largestElementIndex]) {
        largestElementIndex = l;
    }
    int r = rightChild(i);
    if (r &lt; size &amp;&amp; data[r] &gt; 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 &gt;= 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);
    ...
}