堆上的 max_heapify 过程

发布于 2024-10-02 17:06:12 字数 1239 浏览 6 评论 0原文

当我运行时，我有这些程序，

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

它编译得很好，但是在运行停止后，它异常运行，为什么？请帮忙查看来自 Wikipedia 的代码

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)

。

原文

i have these procedure

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

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)

From Wikipedia.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

君勿笑 2024-10-09 17:06:12

您将维基百科文章中的伪代码翻译成 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，这意味着无论如何您都会继续递归。显然你的程序会因堆栈溢出而崩溃。与迭代不同，您不能无限递归，因为您很快就会耗尽堆栈空间。

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)

Translated into C++, this should read something like:

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

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.

回复收藏 0 原文