Как создать метод HeapSort для массива в Java? - PullRequest
Новая
       74

Как создать метод HeapSort для массива в Java?

1 голос
/ 12 мая 2019

Я знаю, что существует множество методов HeapSort для переполнения стека, однако ни один из них не обязательно поможет мне с тем, над чем я работаю.

У меня есть представление о том, что такое куча, я просто не знаю, как обязательно получить эти значения и отсортировать их, чтобы сохранить их в массиве.

Поэтому мои инструкции гласят: метод static heapSort (Comparable [], int) должен выполнять сортировку по месту (от минимального значения к наибольшему значению) массива. Второй параметр указывает количество заполненные элементы в массиве. Чтобы «обработать сам [массив] как max-heap», этот метод может создать локальный экземпляр MaxHeapPriorityQueue и назначить первый параметр elementData, а второй параметр - size. Поскольку данные начинаются с индекса 0, вы не сможете использовать большинство других частных вспомогательных методов. Когда метод завершится, параметр массива будет отсортирован. 

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];
    }
}

Этот алгоритм был основан на моих заметках, однако я в основном борюсь с тем, что я прокомментировал в первой строке метода. Я предоставил два других класса, которые связаны с этим методом. У меня также есть другие методы, но, как я уже говорил ранее в инструкциях, родители, leftChild, rightChild и т. Д. Не будут использоваться. Однако было упомянуто о попытке создать два частных вспомогательных метода, таких как закрытый метод E removeSort () и закрытый метод void bubbleDown (int index).

Ответы [ 2 ]

2 голосов
/ 12 мая 2019

В ревизии 1 вы пытаетесь присвоить что-то PriorityQueue<>. Предполагая , что это java.util.PriorityQueue<>, нет (Java) способа, которым это будет работать, если только что-то не принадлежит к классу, расширяющему java.util.PriorityQueue<>:
даже since 1.5, они не испортили его, не указавинтерфейс, но класс.

Начиная с ревизия 2 , MaxHeapPriorityQueue.heapSort(a, size) выполняет , а не выполняет an "in-place" sort.Классы не связаны с heapSort(a, size).

0 голосов
/ 16 мая 2019

Вот что это. 

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