0
$\begingroup$

Won't both the methods ultimately give a max/min heap? So if I am given a binary tree, as an array, and am asked to convert it to a max heap, can I just use the bottom up construction of the heap?

Bottom up construction method:

void bottomupheap(int arr[size],int n){
    int i,ele,p,c;
    for(i=(n/2)-1;i>=0;i--){
        p=i;
        ele=arr[i];
        int heap=0;
    
        while(!heap&&2*p+1<=n-1){
            c=2*p+1;
            if(c+1<=n-1 && arr[c+1]>arr[c]){
                c=c+1;
            }
            if(arr[c]<ele){
                heap=1;
            }
            else {
                arr[p]=arr[c];
                p=c;
            }    

        }
        arr[p]=ele;
    
    }
    for(i=0;i<n;i++){
        printf("%d",arr[i]);
    }
}

on testing this with the array {10,90,40,5,2} it prints 90,10,40,5,2

$\endgroup$
3
  • 3
    $\begingroup$ Running time complexity in top down approach is $O(n \log n)$ and for the bottom up approach is $O(n)$. $\endgroup$ Nov 27 '21 at 10:26
  • 2
    $\begingroup$ This question and answer explain it all. $\endgroup$
    – Nathaniel
    Nov 27 '21 at 11:31
  • $\begingroup$ Consider changing your code toe a generalized pseudo-code of your function $\endgroup$
    – lox
    Nov 30 '21 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.