有人可以解释为什么这个堆排序实现不起作用吗？

Question

我在这上面花了几个小时，但我是 C++ 面向对象编程的新手，所以可能某些函数参数没有按应有的方式传递，但我找不到它。对于此代码，我得到以下输出：1 2 7 10 3 2 4 15

#include <iostream>

using namespace std;

class Heap {
    int * arrayX, heap_size, length;

private:
    int leftChild(int i) {
        return 2*i;
    }
    int rightChild(int i) {
        return 2*i+1;
    }
public:
    Heap(int * array, int length) {
        this->arrayX = array;
        this->length = length;
        this->heap_size = length;
    }
    void swapA(int &x,int &y)
    {
        int temp=x;
        x=y;
        y=temp;
    }
    void maxHeapify(int index) {
        int left_child = leftChild(index), right_child=rightChild(index), largest;
        if((left_child <= heap_size) && ( arrayX[left_child] > arrayX[index]))
            largest = left_child;
        else
            largest = index;
        if( (right_child <= heap_size) && (arrayX[right_child] > arrayX[index]))
            largest = right_child;
        if(largest != index) {
            swapA(arrayX[index],arrayX[largest]);
            maxHeapify(largest);
        }
    }
    void buildMaxHeap() {
        for(int i=length/2;i>0;i--)
            maxHeapify(i);
    }
    void heapsortF() {
        heap_size = length;
        buildMaxHeap();
        for(int i = heap_size; i>1; i--) {
            swapA(arrayX[1],arrayX[i]);
            heap_size--;
            maxHeapify(1);
        }

    }

    void printHeap() {
        for(int i=1; i<=length; i++)
            cout << arrayX[i] << " ";
        cout << endl;
    }
};


int main() {
    int a[]={0,4,2,3,1,10,15,2,7};
    Heap novi_heap(a, sizeof(a)/sizeof(int)-1);
    novi_heap.heapsortF();
    novi_heap.printHeap();
    return 0;
}

Answer 1

您在 maxHeapify 函数中混淆了 index 和 largest。在第二个 "if" 表达式中，您应该将 right_child 与 largest 进行比较，而不是与 index 进行比较，因为您需要从三个顶点中选择一个具有最大值的顶点：index、left_child 和 right_child.

这是经过更正的代码行，如下所示：

if((right_child <= heap_size) && (arrayX[right_child] > arrayX[largest]))
  largest = right_child;

有人可以解释为什么这个堆排序实现不起作用吗？

Can someone explain why this heapsort implementation doesn't work?

c++

sorting

heapsort

clrs