Получение значений мусора при обходе минимальной кучи

Question

Получение значений мусора при обходе минимальной кучи

Это мой метод обхода:

void heapTraversal(){
for(int i = 0; i<maxsize; i++){
cout << "Current value is : " << hipa[i] << endl;
if(hipa[(2*i)+1]){
cout << "Left child is : " << hipa[(2*i)+1] << endl;
}
else{
cout << "Left child does not exist" << endl;
}
if(hipa[(2*i)+2]){
cout << "Right child is : " << hipa[(2*i)+2] << endl;
}
else{
cout << "Right child does not exist" << endl;
}

Это вывод, который я имею:

Current value is : 7
Left child is : 9
Right child is : 17
Current value is : 9
Left child is : 15
Right child is : 12
Current value is : 17
Left child is : 25
Right child is : 22
Current value is : 15
Left child is : 1769234787
Right child does not exist
Current value is : 12
Left child does not exist
Right child does not exist
Current value is : 25
Left child does not exist
Right child is : 1852112910
Current value is : 22
Left child is : 1395618676
Right child is : 1701994856

Кажется, он работает правильно, но у меня есть все эти значения мусора, которых я не должен был, я не мог точно определить проблему.

Я подозреваю, что с управляющими структурами что-то не так, моя логика верна или я должен был использовать другие операторы if?

-1

c++heap min-heap traversal

Решение

Другие решения

Я исправил проблему, изменив параметр цикла for с maxsize на heap_size.
maxsize должен был быть объемом кучи, а heap_size — текущим размером кучи. Я добавил остальную часть объявления класса для любопытных.

class minHeap{
int *hipa;
int maxsize;
int heap_size;

public:
minHeap(int size);
void minHeapbuild(int );

int root(int i){
return (i-1)/2;
}
int left(int i){
return (2*i+1);
}
int right(int i){
return (2*i+2);
}

int extractRoot();
void decreaseKey(int i, int newKey);
void deleteKey(int key);
void addKey(int key);

int getRoot(){
return hipa[0];
}
}

0

Источник

Accepted Answer

Даже с исправлением, которое вы опубликовали в своем ответе, вы столкнетесь с той же проблемой всякий раз, когда heap_size >= (maxsize/2), Вы должны проверить вычисленные левый и правый дочерние индексы. Исправленный код:

void heapTraversal(){
for(int i = 0; i<heap_size; i++){
cout << "Current value is : " << hipa[i] << endl;
int left = (2*i)+1;

if(left < heap_size && hipa[left]){
cout << "Left child is : " << hipa[left] << endl;
}
else{
cout << "Left child does not exist" << endl;
}

int right = left+1;
if(right < heap_size && hipa[right]){
cout << "Right child is : " << hipa[right] << endl;
}
else{
cout << "Right child does not exist" << endl;
}

0