Как написать метод bubbleDown с кучи в Java? - PullRequest
Новая
       33

Как написать метод bubbleDown с кучи в Java?

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

Я знаю, что есть несколько вопросов, подобных этому, опубликованных по всему переполнению стека, однако ни один на самом деле не отвечает на мой вопрос.Я пишу вспомогательный приватный метод bubbleDown, чтобы помочь мне разобраться в моем общедоступном статическом методе HeapSort.

Я знаю, что идея состоит в том, чтобы рассматривать себя как максимальную кучу, чьи данные начинаются с 0 (не 1).

  • a на самом деле не в порядке кучи.
  • Но если вы неоднократно «пузырите» каждый неконечный узел, начиная с последнего, у вас в итоге будет надлежащая куча.

Я написал этот алгоритм, однако яЯ не уверен, что это точно работает.

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 (Comparable n : a)
    {
        mhpq.bubbleDown((int) n);
    }
    for (int i = 0; i < a.length-1; i++)
    {
        a[i] = mhpq.sortRemove();
    }
}
private void bubbleDown(int index)
{
    boolean found = false;
    while(!found)
    {
        int leftIndex = lChild(index);
        int rightIndex = rightChild(index);
        int largestChildIndex = leftIndex;

        if(hasRChild(index))
        {

     if(elementData[leftIndex].compareTo(elementData[rightIndex]) < 0 )
     {
        largestChildIndex = rightIndex;
     }
}
        if(hasLChild(index))
        {

   if(elementData[largestChildIndex].compareTo(elementData[index]) > 0)
            {
                swap(elementData, largestChildIndex , index);
                index = largestChildIndex;
            }
            else
            {
                found = true;
            }
        }
        else //Probably a leaf
        {
            found = true;
        }
    }
}

Теперь все кажется более плавным, просто, когда у меня есть повторяющиеся значения, они не упорядочены правильно.Я не могу найти эту ошибку в моем методе пузыря.

1 Ответ

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

Вот что я получил 

private void bubbleDown(int index)
{
    boolean found = false;
    while(!found && (2*index +1) < size)
    {
        int left = leftChild(index) + 1;
        int right = rightChild(index) + 1;
        int child = left;

        if((index*2 +2) < size && elementData[right].compareTo(elementData[left]) > 0)
        {
            child = right;
        }
        if(elementData[index].compareTo(elementData[child]) < 0)
        {
            swap(elementData, index, child);
            index = child;
        }
        else
        {
            found = true;
        }
    }
}
...