对最大堆进行排序将返回按降序排序的列表。应该按升序排列吗？

Question

我的教授介绍了如何使用ArrayList创建Max Heap类。然后他让我们写一个maxHeapSort方法。我几乎成功地将堆按降序排序，但我假设排序应该按升序。现在我使用一个最大堆为[11，5，8，3，4，1]的ArrayList，它排序为[11，8，5，3，4，1]。

这是我的maxHeapSort代码：

protected void maxHeapSort() {
    int n = this.heap.size();

    if(this.heap.size() == 0){
        return;
    }

    for(int i = n - 1; i > 0; i --){
        T temp = this.heap.get(0);
        this.heap.set(0, this.heap.get(i));
        this.heap.set(i, temp);

        this.heapifyDown(0);
    }
}

下面是我的教授给出的heapifyDown方法：

protected void heapifyDown(int index){
    // get the left and right children indices
    int leftIndex = 2 * index + 1;
    int rightIndex = 2 * index + 2;

    // set the max to the one that we are trying to heapify
    int maxIndex = index;

    // figure out which value is the max
    if(leftIndex < this.size && this.heap.get(leftIndex).compareTo(this.heap.get(maxIndex)) > 0){
        maxIndex = leftIndex;
    }

    if(rightIndex < this.size && this.heap.get(rightIndex).compareTo(this.heap.get(maxIndex)) > 0){
        maxIndex = rightIndex;
    }

    // do we need to swap and keep heapifying
    if (maxIndex != index) {
        // swap
        T temp = this.heap.get(index);
        this.heap.set(index, this.heap.get(maxIndex));
        this.heap.set(maxIndex, temp);

        // recurse
        this.heapifyDown(maxIndex);
    }

}

这是我的测试代码：

@Test
public void testMaxHeapSort(){
    MaxHeap<Integer> maxHeap = new MaxHeap<>();
    maxHeap.heap.add(11);
    maxHeap.heap.add(5);
    maxHeap.heap.add(8);
    maxHeap.heap.add(3);
    maxHeap.heap.add(4);
    maxHeap.heap.add(1);

    maxHeap.size = 6;

    maxHeap.maxHeapSort();

    assertEquals("[1, 3, 4, 5, 8, 11]", maxHeap.heap.toString());
}

Answer 1

只需更新比较，检查电流是否小于左侧，然后转到左侧，如果电流大于右侧，则转到右侧

    if(leftIndex < this.size && this.heap.get(maxIndex).compareTo(this.heap.get(leftIndex)) < 0) {
        maxIndex = leftIndex;
    }

    if(rightIndex < this.size && this.heap.get(maxIndex).compareTo(this.heap.get(rightIndex)) > 0){
        maxIndex = rightIndex;
    }