heap.cpp

#include <bits/stdc++.h>
using namespace std;

void max_heapify(vector<int>&arr,int i,int N){
    if(i==0 || N==0){
        return;
    }
    int largest,left=2*i,right=2*i+1;
    if(left<=N && arr[left]>=arr[i]){
        largest=left;
    }
    else{
        largest=i;
    }
    if(right<=N && arr[right]>arr[largest]){
        largest=right;
    }

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

void build_maxheap(vector<int>&arr,int N){
    for(int i=N/2;i>=1;i--){
        max_heapify(arr,i,N);
    }
}

void show_heap(vector<int>arr,int N){
    if(N==0){
        cout<<"Heap Removed or Not Formed\n";
        return;
    }
    cout<<"Heap formed :\n";
    for(int i=1;i<=N;i++){
       cout<<arr[i] <<" ";
    }
    cout<<"\n";
}
void Insert(vector<int>&arr,int num,int N){
    arr.push_back(num);
    build_maxheap(arr,N);
}

void Del_heap(vector<int>&arr,int &N){
    if(N==0){
        cout<<"Heap Removed or Not Formed\n";
        return;
    }
    int a=arr[1];
    swap(arr[1],arr[N]);
    N--;
    max_heapify(arr,1,N);
    // cout<<"Deleted "<<a<<"\n";
    // show_heap(arr,N);
}

void heap_sort(vector<int>&arr,int &N){
    int len=N;
    for(int i=2;i<=len;i++){
        Del_heap(arr,N);
    }
    cout<<"Sorted Array is:\n";
    for(int i=1;i<arr.size();i++){
        cout<<arr[i]<<" ";
    }
    cout<<"\n";
}

int main(){
    vector<int>arr;
    int num;
    arr.push_back(-1);
    int N=arr.size()-1;
    // {-1,4,5,1,6,7,3,2};
    cout<<"Enter no in max heap:\n";
    cout<<"To stop enter any character :\n";
    while(cin>>num){
        Insert(arr,num,++N);
    }
    show_heap(arr,N);
    heap_sort(arr,N);
}