Почему мой метод Max Heap Heapsort не работает? - PullRequest
Новая
       74

Почему мой метод Max Heap Heapsort не работает?

1 голос
/ 26 марта 2020

Так что я работаю с java реализацией Max Heaps. Мои методы Insert, bubbleUp и deleteMax (сами по себе), кажется, работают нормально, но мой метод heapsort (который вызывает deleteMax) не работает должным образом (он не вызывает сообщение об ошибке; он просто не сортирует их в том порядке, в котором они должны). Я включил код ниже. Любая помощь в понимании проблемы очень ценится. Спасибо!

Весь класс можно найти по адресу: https://repl.it/repls/FrequentPartialBlockchain

'' '

    public int deleteMax(){
        if(this.numNodes == 0)
            throw new NoSuchElementException();
        else if(this.numNodes == 1){
            int elemToReturn = heapArr[0];
            heapArr[0] = null;
            return elemToReturn;
        }

        int elemToReturn = heapArr[0];
        heapArr[0] = heapArr[numNodes-1];
        heapArr[numNodes-1] = null;
        this.numNodes--;
        bubbleDown();
        return elemToReturn;
    }

    private void bubbleDown(){
        int n = 0;
        int L = 2 * n + 1; // L will hold the index of the left child
        while(L < this.numNodes - 1){
            int max = L;
            int R = L + 1; // R will hold the index of the right child

            if(R < this.numNodes - 1){
                if(heapArr[R] >= heapArr[L])
                    max++;
            }
            int temp;
            if(heapArr[n] < heapArr[max]){
                // swap
                temp = heapArr[n];
                heapArr[n] = heapArr[max];
                heapArr[max] = temp;

                n = max;
                L = 2 * n + 1;
            }
            else{
                break;
            }
        }
    }

    public static void heapsort(Integer[] arrayToSort){
        MaxHeap tempHeap = new MaxHeap(arrayToSort);
        for(int i = 0; i < tempHeap.numNodes; i++)
            arrayToSort[i] = (Integer) tempHeap.deleteMax();
    }

' ''

1 Ответ

0 голосов
/ 26 марта 2020

Этот оператор while кажется неправильным: 

while(L < this.numNodes - 1){

Если this.numNodes - это количество узлов в куче, то this.numNodes - 1 - последний узел. Это условие затем запрещает ввод l oop, если L является последним узлом в куче.

В связанной ноте ваш особый случай в deletMax нарушен. Вы удаляете единственный узел в куче, но забыли установить numNodes в 0.

...