procédure max_heapify sur tas

Question

i ont ces procédures

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

quand je le lance compile bien, mais il est après l'exécution cesse ubnormaly courir pourquoi? s'il vous plaît aider oeil à ce code

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) 

De Wikipedia.

Answer 1

Vous n'avez pas de cas de base pour terminer la récursion, donc j'imagine que vous finissez par avoir un débordement de pile. Pensez à quand vous pouvez dire que vous avez terminé afin que vous puissiez gracieusement tomber hors de la fonction.

Answer 2

Peut-être que vous ne devriez pas toujours appel max_Heapify queue récursive, mais revenir à la place lorsque vous avez atteint la taille fond du tas de tri ... Ce qui se passe est que votre programme fonctionne sur pile. En outre, consultez std::swap.

Answer 3

La fonction max_Heapify est toujours récursivement infinie. Vous voyez un débordement de pile (petit s, petit o).

Si vous passez en revue votre code dans le débogueur, ce genre de chose sera rapidement évident.

Answer 4

Vous avez traduit le pseudo-code de l'article Wikipedia en code C++, mais vous avez accidentellement modifié la logique. Dans l'article de Wikipedia, vous remarquerez que la récursion ne se produit que conditionnelle: c'est if largest ≠ i

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

Traduit en C++, cela devrait lire quelque chose comme:

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

Encore une fois, notez que l'appel récursif à Max_Heapify se produit uniquement conditionnellement, lorsque largest != i. Dans votre code, vous appelez récursivement Max_Heapifyinconditionnellement, ce qui signifie que vous continuez récursif, peu importe quoi. Donc, évidemment, votre programme va se bloquer avec un débordement de pile. Contrairement à l'itération, vous ne pouvez pas vous recurder indéfiniment car vous manquez rapidement d'espace de pile.

Answer 5

Voici la version que j'ai écrite, vous pouvez jeter un oeil.

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