c++ - max_heapify procedure on heap -


i have these procedure

#include <iostream> using namespace std;  int parent(int ){     return  i/2; }  int left(int ){     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);      (int i=0;i<n;i++){          cout<<a[i]<<"  ";      }     return 0; } 

when run compiles fine after run stops ubnormaly it's running why? please @ code

max-heapify[2](a, i):  left ← 2i  right ← 2i + 1  largest ←  if left ≤ heap-length[a] , a[left] > a[i] then:  largest ← left  if right ≤ heap-length[a] , a[right] > a[largest] then:  largest ← right  if largest ≠ then:  swap a[i] ↔ a[largest]  max-heapify(a, largest) 

from wikipedia.

you translated pseudo-code wikipedia article c++ code, accidentally altered logic. in wikipedia article, you'll notice recursion happens conditionally: is, if largest ≠ i

if largest ≠ then:     swap a[i] ↔ a[largest]     max-heapify(a, largest) 

translated c++, should read like:

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

again, notice recursive call max_heapify happens conditionally, when largest != i. in code, recursively call max_heapify unconditionally, meaning keep recursing no matter what. program going crash stack overflow. unlike iteration, can't recurse infinitely because run out of stack space.


Comments

Popular posts from this blog

c++ - How to modify context menu of internet explorer using IDocHostUIHandler::ShowContextMenu? -

android - Spacing between the stars of a rating bar? -

c# - Getting "Internal .Net Framework Data Provider error 30" error when column has NULL value -