如何在Java中为MaxHeapPriorityQueue编写sortRemove方法？

Question

我正在为我的HeapSort静态方法开发一个辅助方法私有E sortRemove（）。让我注意一下，这个堆是一个MaxHeapPriorityQueue，它的所有元素都有一个子元素，其值小于父元素。

我正在努力

• 重复调用删除，直到堆为空。
• 但是，当一个元素被“删除”时，它被移动到数组的末尾，而不是完全从数组中逐出。
• 当你完成时，瞧！数组已排序。

我试图弄清楚如何让这个算法适合我的代码。

因此我有：

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

我知道这不一定是正确的算法，但根据我的理解，我想得到第一个最大的值，作为列表中的最后一个元素，它以这种方式排序。堆排序方法也不一定准确，因此，我还有另一个问题（如何在Java中创建一个数组的堆排序方法？），在这个方法中，我想主要关注sortRemove方法。

Answer 1

这是我想出来的

我们将原始值存储在某个地方以供保存。

然后将第一个值索引更改为最后一个，并减小大小。

然后我们只在索引0处冒泡。

然后返回值。

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

Answer 2

就地堆排序包括两个步骤：

< li >从任意数组创建堆。 < li >重新排列生成的数组，以便对其进行排序。

您可以通过使用生成Heap算法在O（n）时间内完成第一步。我在下面展示基本思想。假设一个长度为 n 的数组 a。

for i = (n-1)/2 downto 0
    bubbleDown(i);

请注意，您从中间开始，然后回到数组的开头。让我举个例子来说明它是如何工作的。假设您得到了数组 [1，5，3，4，6，7，2]。表示为二进制堆，即变为：

        1
    5       3
 4    6   7   2

< code>(n-1)/2是3，所以我们从堆中的值< code>4开始。不能移动，所以我们使用值< code>3。我们正在构建一个最大堆，所以我们检查两个孩子，看看是否有一个大于3。如果是这样，我们就和两个孩子中最大的交换。这给出了:

        1
    5       7
 4    6   3   2

向后移动到值5，我们看到6更大，因此我们交换这两个项目：

        1
    6       7
 4    5   3   2

最后，根元素。7是较大的子元素，所以我们交换：

        7
    6       1
 4    5   3   2

由于尚未达到叶级，我们再次检查并将1与3:

        7
    6       3
 4    5   1   2

在那里你有一个有效的最大堆。此算法始终有效。

请注意，您从根开始并向下工作的想法并不总是会产生有效的堆。以我之前给出的起始位置为例：

        1
    5       3
 4    6   7   2

如果我从顶部开始向下冒泡，那么我们交换< code>1和< code>5，然后我们交换< code>5和< code>6，得到:

        6
    5       3
 4    1   7   2

我们看5，它不需要冒泡。然后我们看3，然后换成7，结果：

        6
    5       7
 4    1   3   2

这样就完成了，因为树叶层不能向下冒泡。最后你得到的树不是有效的堆。

因此，< code>makeHeap来构建堆。

第二步:排序。

创建堆后对数组进行排序非常简单。基本算法是：

while n > 0
    swap(a[0], a[n-1]) // puts the largest item at the end of the heap
    n = n - 1          // decrease remaining count
    bubbleDown(0)      // adjust the heap

这只是对任何max堆实现中的标准removeLargest函数的轻微修改。您不是删除并返回根项，而是将其与堆中的最后一项交换。

让我们看看它是如何工作的。给定起始堆：

        7
    6       3
 4    5   1   2

将 7 换成 2，减少计数，然后向下泡泡：

        6
    5       3
 4    2   1   7

用1替换6，减少计数，向下冒泡:

        5
    4       3
 1    2   6   7

将5与2交换，减少计数，并向下冒泡：

        4
    2       3
 1    5   6   7

将4与1交换，减少计数，并向下冒泡：

        3
    2       1
 4    5   6   7

...我就讲到这里，因为我想你们已经明白了。

这真的很简单。如果您有一个带有insert和removeLargestmethods的max-heap实现，以及标准的 和 bulleDown

建议的heapSort方法：

public static void heapSort(Comparable[] a, int size)
{
  MaxHeapPriorityQueue elementData = new MaxHeapPriorityQueue();
  // PriorityQueue<Comparable> pq = new PriorityQueue();

  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
  }
  // The array is sorted.
}