Куча массив не работает
Я пишу программу для построения массива кучи из обычного массива, и он просто не работает.
Мы должны использовать этот код sudo, который я использовал для написания своей функции rebuildHeap, но я не знаю, что я делаю неправильно. Может ли кто-нибудь заметить какие-либо ошибки?
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 и сохраняю некоторые случайные значения, затем запускаю функцию create heap, которая вызывает rebuildHeap до тех пор, пока массив 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;
}
};
Решение
Прежде всего, я хотел бы подчеркнуть, что ваш перевод псевдокода был неверным, поэтому я исправил его.
#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, поэтому я не уверен, каков ваш ожидаемый результат.
Другие решения