Массивное представление максимальной кучи

Question

Массивное представление максимальной кучи

Я пытаюсь создать максимальную кучу, логика проста, если parent меньше, чем один из его childre, меняйте их местами. Я пытался реализовать это с помощью

void maxHeapify( int i , int *a , int n ){

int largest = i;
int left    = ( i * 2 ) + 1;
int right    = ( i * 2 ) + 2;

if( left < n && a[ largest] < a[ left ])
largest = left;
if( right < n  && a[ largest ] < a[right])
largest = right;
if( largest != i ){
swap( a[i], a[largest]);
maxHeapify( largest , a,  n );
}
}int main(){
int n;
int * a;
cout << "Number of elements : ";
cin >> n ;
a = new int[n];
for( int i = 0; i < n ; i++){
cin >> a[i];
}

for( int i = n/2 -1 ; i >= 0 ; i-- ){
maxHeapify( i , a, n);
}
for(int i = 0; i < n ; i++){
cout << a[i] << " ";
}

return 0;
}

я использую ввод

2 7 26 25 19 17 1 90 3 36

дерево должно выглядеть

поэтому представление массива должно быть 90 36 17 25 26 7 1 2 3 19
все же вывод кода

90 36 26 25 19 17 1 7 3 2

я посмотрел его и нашел много одинаковых кодов во многих уроках. Почему на выходе нет представления дерева в массиве? Я неправильно понял?

Спасибо за объяснение

2

c++heap max-heap

Решение

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

Окончательная структура кучи зависит от порядка вставки и исходной структуры. В твоем случае, 2 7 26 25 19 17 1 90 3 36 приведет к ожидаемому результату, если вы начнете с пустой кучи, вставляете элементы в заданном порядке и складываетесь в кучу после каждой вставки.

Этот код даст ожидаемый результат:

std::vector<int> b = {2, 7, 26, 25, 19, 17, 1, 90, 3, 36};
auto it = b.begin();
while (it != b.end())
{
std::make_heap(b.begin(), it+1);
++it;
}

Однако, что делает ваш код, это предварительно вставляет все элементы в кучу, а затем упорядочивает его, эквивалентно этому:

std::vector<int> b = {2, 7, 26, 25, 19, 17, 1, 90, 3, 36};
std::make_heap(b.begin(), b.end());

Оба результата одинаково действительны.

0

Источник

Accepted Answer

Почему вы ожидаете, что ваша куча будет выглядеть определенным образом? Есть много способов, которыми эти входные числа могут быть организованы в кучу. Результат, который вы получаете, также является допустимой кучей — каждый родительский размер больше, чем его дочерние элементы:

        90
36      26
25   19  17  1
7 3  2

0