java - 如何在 Java 中为数组创建 HeapSort 方法？

Question

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

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

因此，我的说明是这样的:静态 heapSort(Comparable[], int) 方法应该执行数组的“就地”排序(从最低值到最高值)。第二个参数表示的数量数组中的填充元素。为了“将 [数组] 本身视为最大堆”，此方法可以创建本地 MaxHeapPriorityQueue 实例并将第一个参数分配给 elementData，将第二个参数分配给 size。因为数据从索引 0 开始，所以您可能无法使用大多数其他私有(private)帮助器方法。方法完成后，将对数组参数进行排序。

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

这个算法是建立在我的笔记上的，但是我主要是在努力解决我在方法第一行的评论。我提供了与此方法相关的另外两个类。我还有其他方法，但正如我在前面的说明中所述，不会使用 parent、leftChild、rightChild 等。但是，有人提到尝试创建两个私有(private)辅助方法，例如私有(private) E removeSort() 和私有(private) void bubbleDown(int index) 方法。

Answer 1

在revision 1 ，您尝试将某些内容分配给 PriorityQueue<> . 假设这是java.util.PriorityQueue<> ，没有(Java)方法可以工作，除非它属于扩展 java.util.PriorityQueue<> 的类:
甚至 since 1.5 ，他们搞砸了，没有指定接口(interface)，而是指定了类。

---

截至revision 2 , MaxHeapPriorityQueue.heapSort(a, size) 不执行an "in-place" sort .没有类(class)绑定(bind) heapSort(a, size) .