如何为 Java 中的数组创建 HeapSort 方法？

Question

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

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

因此，我的说明是：静态 heapSort(Comparable[], int) 方法应该对数组执行 "in-place" 排序（从最低值到最高值）。第二个参数表示的数量数组中的填充元素。 To "treat [the array] itself as a max-heap"，这个方法可以创建一个本地的MaxHeapPriorityQueue实例，并将第一个参数赋给elementData，第二个参数赋给size。因为数据从索引 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];
    }
}

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

Answer 1

在 revision 1 中，您尝试将某些内容分配给 PriorityQueue<>。假设这是java.util.PriorityQueue<>，没有（Java）方法可以工作，除非是class扩展java.util.PriorityQueue<>:
甚至 since 1.5，他们也没有指定接口，而是 class.

自 revision 2 起，MaxHeapPriorityQueue.heapSort(a, size) 未执行 an "in-place" sort。没有 class 与 heapSort(a, size).

如何为 Java 中的数组创建 HeapSort 方法？

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

java

arrays

algorithm

heap

heapsort