How to create a HeapSort method to an array in Java?

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.

The wording your "instructions" is not what I would expect. Is MaxHeapPriorityQueue something well known? How would an "instance" have "parameter"s to assign to? What are "the other private helper methods"? Floyd's variation does not insert items one by one. That said, I found Java's genericity unwieldy. — greybeard
– greybeard, Commented May 12, 2019 at 3:57
(In revision 2, what I commented on the first line in the method is rather cryptic for lack of that comment.) — greybeard
– greybeard, Commented May 13, 2019 at 6:00
When referring to names from source code, placing them in ` "backticks" makes that obvious. I find it helpful to decorate method members like leftChild(). — greybeard
– greybeard, Commented May 13, 2019 at 6:18

greybeard · Accepted Answer · 2019-05-13 06:14:37Z

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).

edited May 13, 2019 at 6:14

answered May 12, 2019 at 15:27

greybeard

2,6779 gold badges40 silver badges71 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Adan Vivero Over a year ago

Oh alright, but what do you recommend for that line, because if I get that line figured out, I can figure out the whole algorithm to finish it off.

Adan Vivero Over a year ago

Alright, well I edited my code up above, I commented out a line that I used previously, however the only problem I have now is just making it all sorted algorithm.

Adan Vivero Over a year ago

I was given two private helper methods such as a private E removeSort() and a private void bubbleDown(int index) method. I'm still unsure on how I would use those, but if I have issues with them I will ask a question. So far when I run tests, it just says it's unsorted.

Adan Vivero · Accepted Answer · 2019-05-15 22:00:08Z

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();
    }
}

answered May 15, 2019 at 22:00

Adan Vivero

43213 silver badges41 bronze badges

Collectives™ on Stack Overflow

How to create a HeapSort method to an array in Java?

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related