如何在Java中为MaxHeapPriorityQueue编写sortRemove方法？ [英] How to write a sortRemove method for MaxHeapPriorityQueue in Java?

问题描述

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

I am working on a helper method private E sortRemove(), for my HeapSort static method. Let me note, that this heap is a MaxHeapPriorityQueue, which all the elements have a child that has a value that is smaller than the parent.

我正在尝试

• 反复调用remove直到堆为空。


• 但是要做到这样，以便在删除元素时将其移到数组的末尾，而不是完全从数组中移出。


• 完成后，瞧！数组已排序。

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

I'm trying to figure out how to have this algorithm fit into my code.

因此，我有：

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方法也不一定准确，因此，我还有另一个问题要解决（如何在Java中为数组创建HeapSort方法？），在这一部分中，我主要关注sortRemove方法。

I know this isn't necessarily the correct algorithm, but from my understanding, I want to get the first value which is the largest, to be the last element in the list that way it is sorted. The HeapSort method isn't necessarily accurate either, therefore, I have another question addressing that (How to create a HeapSort method to an array in Java?), in this one, I want to primarily focus on the sortRemove method.

推荐答案

这就是我想出的内容

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

Then change the first value index to be the last and decrement the size.

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

Then we bubble down at only index 0.

然后返回值。

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

这篇关于如何在Java中为MaxHeapPriorityQueue编写sortRemove方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！