如何为Java中的最大堆优先级队列写一个排序删除方法？

Question

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

我正在尝试

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

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

因此我有：

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 方法也不一定准确，因此，我有另一个问题解决这个问题 ()，在这个问题中，我想主要关注 sortRemove 方法。

Answer 1

一个in-place堆排序包括两个步骤：

从任意数组创建堆。
正在重新排列生成的数组以便对其进行排序。

您可以使用 makeHeap 算法在 O(n) 时间内完成第一步。我在下面展示了基本的想法。假设数组 a 的长度为 n.

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。我们正在构建一个最大堆，所以我们检查两个 children 看是否有一个大于 3。如果是，我们交换两个 children 中最大的一个。这给出：

        1
    5       7
 4    6   3   2

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

        1
    6       7
 4    5   3   2

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

        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.
}

Answer 2

这是我想出的

我们将该原始值存储在某处以供保存。

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

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

然后我们return这个值。

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

如何为Java中的最大堆优先级队列写一个排序删除方法？

How to write a sortRemove method for MaxHeapPriorityQueue in Java?

java

arrays

heap

priority-queue

heapsort