堆上的max_heapify过程 [英] max_heapify procedure on heap
问题描述
我有这些程序
#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它正在运行为什么?请帮助
查看此代码
when i run it compiles fine but after run stops ubnormaly it's running why? please help look at this 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)
从维基百科。
推荐答案
将维基百科文章中的伪代码翻译成C ++代码,你不小心改变了逻辑。在维基百科文章中,您会注意到递归只会有条件地在 发生: if most≠i
You translated the pseudo-code from the Wikipedia article into C++ code, but you accidentally altered the logic. In the Wikipedia article, you'll notice that the recursion only happens conditionally: that is, if largest ≠ i
if largest ≠ i then:
swap A[i] ↔ A[largest]
Max-Heapify(A, largest)
翻译成C ++,应该是这样:
Translated into C++, this should read something like:
if (largest != i) {
swap(a[i], a[largest]);
Max_Heapify(largest);
}
再次注意,递归调用 Max_Heapify
仅在 largest!= i
时有条件地发生。在您的代码中,您可以无条件地递归调用 Max_Heapify
,这意味着无论什么都保持递归。所以显然你的程序将崩溃与堆栈溢出。与迭代不同,你不能无限递归,因为你很快用完了堆栈空间。
Again, notice that the recursive call to Max_Heapify
only happens conditionally, when largest != i
. In your code, you recursively call Max_Heapify
unconditionally, meaning that you keep recursing no matter what. So obviously your program is going to crash with a stack overflow. Unlike iteration, you can't recurse infinitely because you quickly run out of stack space.
这篇关于堆上的max_heapify过程的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!