How to create a HeapSort method to an array in Jav

Question

I know there are countless of HeapSort methods on Stack Overflow, however none necessarily help me with what I am working on.

I have somewhat of an idea what a Heap is, I just don't know how to necessarily grab those value and sort them out to store them into an array.

Therefore, my instructions read: The static heapSort(Comparable[], int) method should perform an "in-place" sort (from lowest value to highest value) of the array. The second parameter indicates the number of filled elements in the array. To "treat [the array] itself as a max-heap", this method can create a local MaxHeapPriorityQueue instance and assign the first parameter to elementData and the second parameter to size. Because the data begins at index 0, you may not be able to use most of the other private helper methods. When the method has finished, the array parameter will be sorted.

public class MaxHeapPriorityQueue<E extends Comparable<E>>
{
private E[] elementData;
private int size;

@SuppressWarnings("unchecked")
public MaxHeapPriorityQueue()
{
    elementData = (E[]) new Comparable[10];
    size = 0;
}
public static void heapSort(Comparable[] a, int size)
{

MaxHeapPriorityQueue elementData = new MaxHeapPriorityQueue();
//PriorityQueue<Comparable> pq = new PriorityQueue();

    for (Comparable n : a)
    {
        elementData.add(n);
    }
    for (int i = 0; i < size; i++)
    {
        a[i] = elementData.remove();
    }
}
public class MHPQIterator implements java.util.Iterator<E>
{
    private int index;

    public boolean hasNext()
    {
        if(size == 0)
        {
            return false;
        }
        else
        {
            return (index < size);
        }
    }
    public E next()
    {
        index++;
        return elementData[index];
    }
}

This algorithm was founded on my notes, however I am mainly struggling with what I commented on the first line in the method. I provided the two other classes that is tied with this method. I also have other methods, but as I stated earlier in the instructions the parent, leftChild, rightChild, and etc. would not be used. However there was mention of trying to make two private helper methods such as a private E removeSort() and a private void bubbleDown(int index) method.

Answer 1

Here's what it is.

public static void heapSort(Comparable[] a, int size)
{
    MaxHeapPriorityQueue mhpq = new MaxHeapPriorityQueue();
    mhpq.elementData = a;
    mhpq.size = size;

    for (int i = (size/2)-1; i >= 0; i--)
    {
        mhpq.bubbleDown(i);
    }
    for(int i = size-1; i >= 0; i--)
    {
        a[i] = mhpq.sortRemove();
    }
}

Answer 2

In revision 1, you try to assign something to a PriorityQueue<>. Assuming this to be java.util.PriorityQueue<>, there is no (Java) way this will work unless that something is of a class extending java.util.PriorityQueue<>:
even since 1.5, they botched it not specifying an interface, but a class.

---

As of revision 2, MaxHeapPriorityQueue.heapSort(a, size) does not perform an "in-place" sort. No classes are tied with heapSort(a, size).