Max-heap-Implementierung
Folgenden code, um die max-heap-Implementierung
#include<iostream>
#include<math.h>
using namespace std;
#define maxn 1000
int x[maxn];
int parent(int i){
return int(i/2);
}
int left(int i){
return 2*i;
}
int right(int i){
return 2*i+1;
}
void max_heap(int x[],int i,int size){
int largest;
int l=left(i);
int r=right(i);
if (l<=size && x[l]>x[i]){
largest=l;
}
else
{
largest=i;
}
if (r<=size && x[r]>x[largest]){
largest=r;
}
if (largest!=i) { int s=x[i];x[i]=x[largest];x[largest]=s;}
max_heap(x,largest,size);
}
int main(){
x[1]=16;
x[2]=4;
x[3]=10;
x[4]=14;
x[5]=7;
x[6]=9;
x[7]=3;
x[8]=2;
x[9]=8;
x[10]=1;
int size=10;
max_heap(x,2,size);
for (int i=1;i<=10;i++)
cout<<x[i]<<" ";
return 0;
}
Wenn ich es laufen lasse, schreibt es eine solche Art der Warnung:
1>c:\users\datuashvili\documents\visual studio 2010\projects\heap_property\heap_property\heap_property.cpp(36): warning C4717: 'max_heap' : recursive on all control paths, function will cause runtime stack overflow
Bitte sagen Sie mir, was ist falsch?
- Was soll dieser code? (andere, die andernfalls während der Kompilierung)
- Lesen Sie in diesem wiki-Artikel über Rekursion.Rekursion
Du musst angemeldet sein, um einen Kommentar abzugeben.
Die Nachricht, die Ihnen genau sagt, was falsch ist. Sie haben noch nicht implementiert, alle Prüfungen zu stoppen die Rekursion. Ein intelligenter compiler.
max_heap
Funktion nicht haben, base case, d.h., eine return-Anweisung. Sie sind nur den rekursiven Aufruf der Funktion aber nie sagen, Wann Sie Pause ein weiteres sukzessiven Aufruf dermax_heap
.Auch, in deinem Beispiel sind Sie nur den Aufruf der Funktion mit out-befriedigend jedem Zustand. In der Regel ist die Rekursion getan oder nicht getan, wenn ein Fall zufrieden.
max_heap
in diesem Fall.max_heap(x,largest,size);
wird nur aufgerufen, wobei sich die Befriedigung jeden Fall. Es inturns machen einen weiteren Anruf und ein anderes machen und so weiter ... Mit einer return-Anweisung endet nur eine solche nennen, aber was ist mit den anderen fordert. Sie können wiederum andere Kette nennt. Bitte Lesen Sie den wiki-link.Einem anderen problem, das ich sehe, ist, dass die Größe des array x ist 10. Aber die Indizes, die Sie verwenden, um Werte sind von 1-10.
Setzen
innerhalb der letzten überprüfung, wie diese:
fertig!
Gibt es viele andere Probleme mit Ihrem code, sondern die Antwort auf Ihre spezifische Frage, über der Veränderung tun würde!