процедура max_heapify для кучи

Question

у меня есть эти процедуры

#include <iostream>
using namespace std;

int parent(int i ){
    return  i/2;
}

int left(int i ){
    return  2*i;
}

int right(int i){
    return 2*i+1;    
}

int a[]={ 27,17,3,16,10,1,5,7,12,4,8,9,10};
int n=sizeof(a)/sizeof(int);

void max_Heapify(int i){
    int largest=0;
    int l=left(i);
    int r=right(i);
    if(l<=n && a[l]>a[i]){
        largest=l;
    }
    else{
        largest=i;
    }
    if(r< n && a[r]>a[largest]){
        largest=r;
    }
    if (largest!=i){
        int t=a[i];
        a[i]=a[largest];
        a[largest]=t;
    }
    max_Heapify(largest);
}

int main(){
     max_Heapify(2);
     for (int i=0;i<n;i++){
         cout<<a[i]<<"  ";
     }    
return 0;
}

, когда я запускаю, он компилируется нормально, но после остановки запуска неожиданно он работает, почему?Пожалуйста, помогите взглянуть на этот код

Max-Heapify[2](A, i):
 left ← 2i
 right ← 2i + 1
 largest ← i
 if left ≤ heap-length[A] and A[left] > A[i] then:
 largest ← left
 if right ≤ heap-length[A] and A[right] > A[largest] then:
 largest ← right
 if largest ≠ i then:
 swap A[i] ↔ A[largest]
 Max-Heapify(A, largest)

Из Википедия .

Answer 1

Вы перевели псевдокод из статьи в Википедии в код C ++, но вы случайно изменили логику.В статье в Википедии вы заметите, что рекурсия происходит только условно : то есть if largest ≠ i

if largest ≠ i then:
    swap A[i] ↔ A[largest]
    Max-Heapify(A, largest)

В переводе на C ++ это должно выглядеть примерно так:

if (largest != i) {
  swap(a[i], a[largest]);
  Max_Heapify(largest);
}

Опять же, обратите внимание, что рекурсивный вызов Max_Heapify происходит только условно , когда largest != i.В вашем коде вы рекурсивно вызываете Max_Heapify безоговорочно , что означает, что вы продолжаете повторяться независимо от того, что.Итак, очевидно, что ваша программа падает с переполнением стека.В отличие от итерации, вы не можете бесконечно повторяться, потому что у вас быстро заканчивается пространство в стеке.

Answer 2

У вас нет базового варианта для завершения рекурсии, поэтому я полагаю, что в итоге вы получаете переполнение стека. Подумайте о том, когда вы можете сказать, что вы сделали, чтобы вы могли изящно выпасть из функции.

Answer 3

Вот версия, которую я написал, вы можете посмотреть.

http://code.google.com/p/clibutils/source/browse/src/c_heap.c

Answer 4

Функция max_Heapify всегда повторяется бесконечно.Вы видите переполнение стека (small s, small o).

Если вы пошагово просматриваете свой код в отладчике, такие вещи быстро станут очевидными.

Answer 5

Возможно, вам не следует всегда вызывать max_Heapify хвост-рекурсивно, а вместо этого возвращать, когда вы достигнете нижнего размера кучи сортировки ... Что происходит, если в вашей программе заканчиваетсястек.

Кроме того, проверьте std::swap.