Может кто-нибудь объяснить, почему эта реализация heapsort не работает?

Я потратил на это несколько часов, но я новичок в объектно-ориентированном программировании на c ++, поэтому, возможно, некоторые аргументы функций не передаются должным образом, но я не могу их найти. Для этого кода я получаю следующий вывод: 1 2 7 10 3 2 4 15

#include <iostream>

using namespace std;

class Heap {
int * arrayX, heap_size, length;

private:
int leftChild(int i) {
return 2*i;
}
int rightChild(int i) {
return 2*i+1;
}
public:
Heap(int * array, int length) {
this->arrayX = array;
this->length = length;
this->heap_size = length;
}
void swapA(int &x,int &y)
{
int temp=x;
x=y;
y=temp;
}
void maxHeapify(int index) {
int left_child = leftChild(index), right_child=rightChild(index), largest;
if((left_child <= heap_size) && ( arrayX[left_child] > arrayX[index]))
largest = left_child;
else
largest = index;
if( (right_child <= heap_size) && (arrayX[right_child] > arrayX[index]))
largest = right_child;
if(largest != index) {
swapA(arrayX[index],arrayX[largest]);
maxHeapify(largest);
}
}
void buildMaxHeap() {
for(int i=length/2;i>0;i--)
maxHeapify(i);
}
void heapsortF() {
heap_size = length;
buildMaxHeap();
for(int i = heap_size; i>1; i--) {
swapA(arrayX[1],arrayX[i]);
heap_size--;
maxHeapify(1);
}

}

void printHeap() {
for(int i=1; i<=length; i++)
cout << arrayX[i] << " ";
cout << endl;
}
};int main() {
int a[]={0,4,2,3,1,10,15,2,7};
Heap novi_heap(a, sizeof(a)/sizeof(int)-1);
novi_heap.heapsortF();
novi_heap.printHeap();
return 0;
}

-1

Решение

Ты перепутал index а также largest в maxHeapify функция. Во втором выражении «если» вы должны сравнить right_child с largest, не с indexпотому что вам нужно выбрать вершину с максимальным значением из трех вершин: index, left_child а также right_child,

Это исправленная строка кода будет выглядеть так:

if((right_child <= heap_size) && (arrayX[right_child] > arrayX[largest]))
largest = right_child;
1

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

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector