0

我正在从书中的伪代码中实现最大堆，并且在调用“buildMaxHeap”函数后得到了奇怪的结果。例如，具有元素 {20, 5, 10, 12, 15, 8, 2, 6, 2, 9} 的整数数组 intHeap 会产生元素 {20, 1066192077, 15, 12, 9, 10, 2, 6 , 2, 5}。我注意到前 5 个元素几乎是按降序排列的，这令人鼓舞。

到目前为止，这是我的实现（删除了一些不相关的代码）：

#define HEAPSIZE 10
int main()
{   
    int intHeap[HEAPSIZE] = {20, 5, 10, 12, 15, 8, 2, 6, 2, 9};

    std::cout << "Displaying intHeap before buildMaxHeap" << std::endl; 
    displayHeap(intHeap);
    buildMaxHeap(intHeap);
    std::cout << "Displaying intHeap after buildMaxHeap" << std::endl;
    displayHeap(intHeap);

    return 0;
}

// maintains max-heap property for array (sifts down)
template <typename T> void maxHeapify(T* array, int i)
{
    // left, right, and largest are positions in the array
    int left = i*2, right = i*2+1, largest;

    if(left <= HEAPSIZE && array[left] > array[i])
        largest = left;
    else
        largest = i;

    if(right <= HEAPSIZE && array[right] > array[largest])
        largest = right;

    if(largest != i)
    {
        swap(&array[i], &array[largest]);
        maxHeapify(array, largest);
    }
}

// builds the max heap
template <typename T> void buildMaxHeap(T* array)
{
    for(unsigned int i = HEAPSIZE / 2; i >= 1; i--)
        maxHeapify(array, i);
}

我真的很难弄清楚 10 位数字是如何在 array[1] 位置结束的，因为它甚至不属于原始数组。

编辑-> 我想我在那个数组索引问题之后让它工作了。

// maintains max-heap property for array (sifts down)
template <typename T> void maxHeapify(T* array, int i)
{
    // left, right, and largest are positions in the array
    int left = LEFT(i), right = RIGHT(i), largest;

    if(left <= (HEAPSIZE - 1) && array[left] > array[i])
        largest = left;
    else
        largest = i;

    if(right <= (HEAPSIZE - 1) && array[right] > array[largest])
        largest = right;

    if(largest != i)
    {
        swap(&array[i], &array[largest]);
        maxHeapify(array, largest);
    }
}

// builds the max heap
template <typename T> void buildMaxHeap(T* array)
{
    for(int i = (HEAPSIZE-1) / 2; i >= 0; --i)
        maxHeapify(array, i);
}

这似乎与我书中的例子一致。由于某种原因，我还不得不将 buildMaxHeap 中的变量 i 从 unsigned int 更改为普通 int （它显示的值低于 0 ...我认为 unsigned only 可能是正数？有谁知道为什么会发生这种情况？）。

无论如何，感谢您指出数组索引问题！

4

2 回答 2

1

在 C++ 中，数组是从零开始的，即n元素数组使用索引0, 1, ..., n-1。您的代码假定它是基于一个的。

于 2013-12-29T23:47:10.063 回答
0

1）你的调试器告诉你什么？

2) 在你的函数中，如果 left == HEAPSIZE 或 right == HEAPSIZE 怎么办？ 

if(left <= HEAPSIZE && array[left] > array[i])
    largest = left;

if(right <= HEAPSIZE && array[right] > array[largest])

然后您继续访问数组[最大]，这是超出范围的。

于 2013-12-29T23:41:42.203 回答