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; 
} 

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

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) 

От Wikipedia.

Answer 1

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

Answer 2

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

Кроме того, зарегистрируйтесь std::swap.

Answer 3

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

Если вы пройдете через свой код в отладчике, это будет очевидно.

Answer 4

Вы перевели псевдокод из статьи Википедии в код на 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 5

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

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