如何在Java中创建数组的堆排序方法？

Question

我知道Stack Overflow上有无数的HeapSort方法，但是没有一个方法一定能帮助我完成我正在做的事情。

我有点想法什么是堆，我只是不知道如何获取这些值并将它们分类以将它们存储到数组中。

因此，我的指令如下：静态堆排序（Comparable[]，int）方法应该对数组执行“就地”排序（从最低值到最高值）。第二个参数指示数组中填充元素的数量。若要“将 [数组] 本身视为最大堆”，此方法可以创建一个本地 MaxHeap优先级队列实例，并将第一个参数分配给 elementData，将第二个参数分配给大小。由于数据从索引 0 开始，因此您可能无法使用大多数其他私有帮助程序方法。方法完成后，将对数组参数进行排序。

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];
    }
}

这个算法是建立在我的笔记上的，但是我主要纠结于我在这个方法的第一行注释的内容。我提供了与这个方法相关的另外两个类。我也有其他的方法，但是正如我之前在指令中提到的，父类，左类，右类，等等。不会被使用。然而，有人提到尝试创建两个私有的helper方法，比如私有的E removeSort()和私有的void bubbleDown(int index)方法。

Answer 1

这就是它。

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

在修订版1中，您尝试将某些内容分配给PriorityQueue

从修订版 2 开始，最大堆优先级队列（a， size） 不执行“就地”排序。没有类与堆排序（a，大小）绑定。