Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.1 kB
2
Indexable
Never
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void maxheapify(int A[],int i, int size){
    
    int left = (3*i) +1;
    int mid = (3*i) +2;
    int right = (3*i) +3;
    int largest=i;
    if(left<size && A[left]>A[i]){
        largest = left;
    }
    
    if(mid< size && A[mid]>A[largest]){
            
        largest = mid;
        
    }
     if(right<= size && A[right]>A[largest]){
        largest = right;
    }
     if(largest != i){
        swap(A[i],A[largest]);
        maxheapify(A,largest,size);
    }
    
    
}
void buildMaxHeap(int A[],int size){
        for(int i = size/3 ; i>=0; i--){
            maxheapify(A,i,size);
           
        }
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    buildMaxHeap(arr,n);
    for(int i=0 ; i<n; i++){
        cout<<arr[i]<<" ";
    }
    
    return 0;
}