如何在Java中为数组创建HeapSort方法？ [英] How to create a HeapSort method to an array in Java?

问题描述

我知道Stack Overflow上有不计其数的HeapSort方法，但是并不一定能帮助我完成我的工作。

I know there are countless of HeapSort methods on Stack Overflow, however none necessarily help me with what I am working on.

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

I have somewhat of an idea what a Heap is, I just don't know how to necessarily grab those value and sort them out to store them into an array.

因此，我的说明如下：静态heapSort（Comparable []，int）方法应执行以下操作的就地排序（从最低值到最高值）：数组。第二个参数指示数组中
个填充元素的数量。为了将数组本身作为最大堆进行处理，此方法可以创建一个本地MaxHeapPriorityQueue实例，并将第一个参数分配给elementData，将第二个参数分配给size。由于数据从索引0开始，因此您可能无法使用大多数其他私有帮助器方法。方法完成后，将对数组参数进行排序。

Therefore, my instructions read: The static heapSort(Comparable[], int) method should perform an "in-place" sort (from lowest value to highest value) of the array. The second parameter indicates the number of filled elements in the array. To "treat [the array] itself as a max-heap", this method can create a local MaxHeapPriorityQueue instance and assign the first parameter to elementData and the second parameter to size. Because the data begins at index 0, you may not be able to use most of the other private helper methods. When the method has finished, the array parameter will be sorted.

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）方法。

This algorithm was founded on my notes, however I am mainly struggling with what I commented on the first line in the method. I provided the two other classes that is tied with this method. I also have other methods, but as I stated earlier in the instructions the parent, leftChild, rightChild, and etc. would not be used. However there was mention of trying to make two private helper methods such as a private E removeSort() and a private void bubbleDown(int index) method.

推荐答案

这就是它。

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

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