c++ - 这个重新堆函数的错误逻辑在哪里？

Question

我目前正在使用一个堆结构，该结构应该用于对数组中的数字进行排序。当我从堆中弹出(出列)一个元素时，我想对结构进行排序时，我在代码中做了类似的事情。

template<typename T>
inline void dHeap<T>::reHeapDown(int root, int bottom)
{
    int minChild;
    int rightChild;
    int leftChild;
    int temp;



// Get index of root's right/left child
leftChild = root * 2 + 1;
rightChild = root * 2 + 2;

//Then we are not done with re-heaping
if (leftChild <= bottom)
{
    if (leftChild == bottom)
    {
        minChild = leftChild;
    }

    else
    {
        if (arr[leftChild] <= arr[rightChild])
            minChild = leftChild;
        else
            minChild = rightChild;
    }

    if (arr[root] > arr[minChild])
    {
        // Swap these two elements
        temp = arr[root];
        arr[root] = arr[minChild];
        arr[minChild] = temp;
        // Make recursive call till reheaping completed
        reHeapDown(minChild, bottom);
    }
}
}

我的想法是，堆中的最低值总是在根中，这就是我将在弹出函数中弹出(出队)的值。但是我遇到了一些问题，它不能正确地对堆进行排序。我在这个函数中的逻辑有问题吗？如果有，它在哪里？

Answer 1

构建堆只强制执行属性:

• 在最小堆的情况下，每个父项都小于它的子项
• 在最大堆的情况下，每个父项都大于其子项。
• 在最小-最大堆的情况下，偶数深度级别 (0,2,4..) 较小，奇数级别 (1,3,5...) 大于它们各自的子级。

但是堆不一定会被排序。它将是平衡的，因为它是按顺序从左到右逐层填充的。

Heapsort将使用堆函数对数组进行排序。最终的数组也将作为一个平衡和排序的堆。