How to write a sortRemove method for MaxHeapPriorityQueue in Java?

Question

I am working on a helper method private E sortRemove(), for my HeapSort static method. Let me note, that this heap is a MaxHeapPriorityQueue, which all the elements have a child that has a value that is smaller than the parent.

I am trying to

• Call remove repeatedly until the heap is empty.
• But make it so that when an element is "removed", it is moved to the end of the array instead of completely evicted from the array.
• When you are done, voila! The array is sorted.

I'm trying to figure out how to have this algorithm fit into my code.

Therefore I have :

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 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();
    }
}
private E sortRemove()
{
    for (int i = (size-1)/2; i >= 0; i--)  //down to 0
    {
        bubbleDown(i);
    }
    while(size > 0)
    {
        swap(elementData, size, 0); // puts the largest item at the end of the heap
        size = size - 1;          // decrease remaining count
        bubbleDown(0);    // adjust the heap
    }
    return sortRemove();
}
}

I know this isn't necessarily the correct algorithm, but from my understanding, I want to get the first value which is the largest, to be the last element in the list that way it is sorted. The HeapSort method isn't necessarily accurate either, therefore, I have another question addressing that (How to create a HeapSort method to an array in Java?), in this one, I want to primarily focus on the sortRemove method.

Answer 1

Here's what I came up with

We store that original value somewhere for it to be saved.

Then change the first value index to be the last and decrement the size.

Then we bubble down at only index 0.

Then we return the value.

private E sortRemove()
{
    E value = elementData[0];
    elementData[0] = elementData[size-1];
    size--;
    bubbleDown(0);
    return value;
}