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

Question

我正在为我的 HeapSort 静态方法开发一个辅助方法 private E sortRemove()。请注意，这个堆是一个 MaxHeapPriorityQueue，其中所有元素都有一个子元素，该子元素的值小于父元素。

我正在努力

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

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

因此我有:

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

我知道这不一定是正确的算法，但根据我的理解，我想获得最大的第一个值，作为列表中排序方式的最后一个元素。 HeapSort 方法也不一定准确，因此，我有另一个问题来解决这个问题 ( How to create a HeapSort method to an array in Java? )，在这个问题中，我想主要关注 sortRemove 方法。

Answer 1

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

1. 从任意数组创建堆。
2. 重新排列生成的数组以使其排序。

您可以使用 makeHeap 算法在 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

(n-1)/2 是 3，所以我们从堆中的值 4 开始。那不能移动，所以我们转到值 3。我们正在构建一个最大堆，所以我们检查两个 child ，看是否有一个大于 3。如果是，我们与两个 child 中最大的一个交换。这给出了:

        1
    5       7
 4    6   3   2

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

        1
    6       7
 4    5   3   2

最后是根元素。 7 是 child 中较大的一个，所以我们交换:

        7
    6       1
 4    5   3   2

因为我们还没有到达叶级，我们再次检查并将 1 与 3 交换:

        7
    6       3
 4    5   1   2

你有一个有效的最大堆。此算法总是有效。

请注意，您从根开始向下处理的想法并不总是会产生有效的堆。采取我之前给出的起始位置:

        1
    5       3
 4    6   7   2

如果我从顶部开始向下冒泡，那么我们交换 1 和 5，然后我们交换 5 和 6，给出:

        6
    5       3
 4    1   7   2

我们看 5，它不需要冒泡。然后我们查看 3 并与 7 交换，结果是:

        6
    5       7
 4    1   3   2

你已经完成了，因为叶级别无法向下冒泡。你最终会得到一个不是有效堆的树。

因此，makeHeap 来构建堆。

第 2 步:排序。

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

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

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

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

        7
    6       3
 4    5   1   2

将 7 与 2 交换，减少计数，然后向下冒泡:

        6
    5       3
 4    2   1   7

将 6 与 1 交换，减少计数，然后向下冒泡:

        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 和 removeLargest 方法的最大堆实现，以及标准的 siftUp 和 bubbleDown (或其他你调用它们)辅助方法，然后添加排序方法就是创建调用辅助方法的这两个小函数。

推荐的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.
}