java为什么我的Max Heap Heapsort方法不起作用？

Question

因此，我正在使用最大堆的java实现。我的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();
    }

'''

Answer 1

这个while语句似乎是错误的：

while(L < this.numNodes - 1){

如果this.numNodes是堆中的节点数，则this.numNodes - 1是最后一个节点。因此，如果L是堆中的最后一个节点，则此条件将阻止进入循环

在一个相关的注释中，您在deletMax中的特殊情况被破坏了。删除堆中唯一的节点，但忘记将numNodes设置为0