我有这些程序
#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)
来自Wikipedia .
最佳答案
您将维基百科文章中的伪代码翻译成 C++ 代码,但您不小心更改了逻辑。在维基百科文章中,您会注意到递归仅有条件发生:也就是说,如果最大≠ 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
,这意味着无论如何您都会继续递归。显然你的程序会因堆栈溢出而崩溃。与迭代不同,您不能无限递归,因为您很快就会耗尽堆栈空间。
关于c++ - 堆上的 max_heapify 过程,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4185139/