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

Я знаю, что есть несколько подобных вопросов, размещенных по всему переполнению стека, однако ни один из них не отвечает на мой вопрос. Я пишу вспомогательный частный метод 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;
        }
    }
}

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


java heap priority-queue bubble-sort heapsort
person Adan Vivero    schedule 14.05.2019    source источник
comment
Этот вопрос также связан с двумя другими моими предыдущими вопросами, которые я задал stackoverflow.com/questions/56095187/ и stackoverflow.com/questions/56119836/   -  person Adan Vivero    schedule 15.05.2019

Ответы (1)


arrow_upward
1
arrow_downward

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

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;
        }
    }
}
person Adan Vivero    schedule 16.05.2019