-2

我正在编写一个程序来从一个普通的数组构建一个堆数组，但它不起作用。我们必须使用我用来编写rebuildHeap 函数的sudo 代码，但我不知道我做错了什么。有人能发现任何错误吗？

rebuildHeap is used after the replacement node has taken the place of root

rebuildHeap(heap, index, lastIndex)
1 if (index * 2 + 1 <= lastIndex)
  1 leftKey = heap[index*2+1].key
  2 if (index * 2 + 2 > lastIndex)
    1 largeChildIndex = index * 2 + 1
  3 else 
    1 rightKey = heap[index*2+2].key
    2 if (leftKey > rightKey)
          1 largeChildIndex = index * 2 + 1
    3 else
          1 largeChildIndex = index * 2 + 2
   4 end if
  4 end if
  5 if (heap[index].key < heap[largeChildIndex].key)
   1 swap (heap[index], heap[largeChildIndex])
   2 rebuildHeap(heap, largeChildIndex, lastIndex)
  6 end if
2 end if

这是我的代码..所以首先我创建一个int数组并存储一些随机值然后我运行调用rebuildHeap的create heap函数直到堆数组完成。

已编辑，删除了数组大小..

void rebuildHeap(int heap[], int index, int lastindex) {
int leftkey = 0 ;
int largeChildIndex = 0;
int rightkey = 0;
cout << endl;

if (heap[index*2+1] <= heap[lastindex])
{
    leftkey = heap[index*2+1];
    cout <<" index : "  << index*2+1 << " leftkey  " << leftkey << endl;
    cout <<" index : "  << lastindex << " heap[lastindex] = " << heap[lastindex] <<       endl;


    if ((heap[index * 2+ 2]) > heap[lastindex])
        largeChildIndex = (index* 2) +1;

    else
    {
        rightkey = heap[index*2+2];

        if (leftkey > rightkey)
            largeChildIndex = index * 2  +1;
        else
            largeChildIndex = index*2+2;
    }
}

if (heap[index] < heap[largeChildIndex]) {
    swap(heap[index], heap[largeChildIndex]);
    rebuildHeap(heap, largeChildIndex, lastindex);
}
}


void swap (int &a, int &b) {
int temp = b;
b = a;
a = temp;
}


int main(int argc, const char * argv[])
{

int a[]  = {3, 7, 12, 15, 18, 23, 4, 9, 11, 14, 19, 21};

int length = (sizeof(a)/sizeof(a[0]));
for (int i = length/2-1; i >= 0; i-- ) {
    rebuildHeap(a, i, length-1);
    cout << " i " << i;
}

for (int i = 0; i < length; i++) {
    cout << endl<< a[i] << endl;
}

 };
4

1 回答 1

1

首先，我想强调您对伪代码的翻译是错误的，所以我修复了它。

#include <iostream>

using namespace std;

void rebuildHeap(int *heap, int index, int lastindex)
{
    int leftkey = 0 ;
    int largeChildIndex = 0;
    int rightkey = 0;

    if ((index*2 + 1) <= lastindex)
    {
        leftkey = heap[index*2+1];

        if ((index*2 + 2) > lastindex)
            largeChildIndex = index*2 +1;

        else
        {
            rightkey = heap[index*2+2];

            if (leftkey > rightkey)
                largeChildIndex = index*2+1;
            else
                largeChildIndex = index*2+2;
        }
    }
    else
    {
        return;
    }
    if (heap[index] < heap[largeChildIndex]) {
        swap(heap[index], heap[largeChildIndex]);
        rebuildHeap(heap, largeChildIndex, lastindex);
    }

}


void swap (int &a, int &b) {
int temp = b;
b = a;
a = temp;
}


int main(int argc, const char * argv[])
 {

int a[]  = {3, 7, 12, 15, 18, 23, 4, 9, 11, 14, 19, 21};

int length = sizeof(a)/sizeof(a[0]);

//create heap
for (int i = (length/2-1); i >= 0; i --)
{
    rebuildHeap(a, i, length-1);
}

//prints the heap array
for (int i = 0; i < length; i++) {
    cout << a[i] << " ";
}

return 0;
}

这是输出：23 19 21 15 18 12 4 9 11 14 7 3

我对堆的理解就像 0，所以我不确定你的预期输出是什么。

于 2014-06-05T08:56:11.977 回答