Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int length = 1 ,c = 1;
- class Heap
- {
- public:
- Build_MaxHeap(int arr[])
- {
- int n = length;
- for(int i=n/2;i>=1;i--)
- Max_heapify(arr,i,n);
- }
- Max_heapify(int arr[],int i,int n)
- {
- int leftchild = 2*i;
- int rightchild = 2*i+1;
- int largest;
- if(leftchild<=n && arr[leftchild]>arr[i])
- largest = leftchild;
- else
- largest = i;
- if(rightchild <=n && arr[rightchild]>arr[largest])
- largest = rightchild;
- if(largest != i)
- {
- swap(arr[largest],arr[i]);
- Max_heapify(arr,largest,n);
- }
- }
- Build_MinHeap(int arr[])
- {
- int n = length;
- for(int i=n/2;i>=1;i--)
- Min_heapify(arr,i,n);
- }
- Min_heapify(int arr[],int i,int n)
- {
- int leftchild = 2*i;
- int rightchild = 2*i+1;
- int smaller;
- if(leftchild<=n && arr[leftchild]<arr[i])
- smaller = leftchild;
- else
- smaller = i;
- if(rightchild <=n && arr[rightchild]<arr[smaller])
- smaller = rightchild;
- if(smaller != i)
- {
- swap(arr[smaller],arr[i]);
- Min_heapify(arr,smaller,n);
- }
- }
- Heap_Sort(int arr[],int n)
- {
- Build_MaxHeap(arr); ///For Sorting First Built Max Heap
- for(int i = 0;i<n;i++)
- {
- swap(arr[1],arr[n-i]); /// Swap 1st and last element of Max heap since 1st element is the MAX element
- Max_heapify(arr,1,n-i-1); /// call Max_heapify without last element and again 1st element will be the MAX element
- }
- }
- void check(int arr[],int i,int n)
- {
- int l = 2*i;
- int r = 2*i+1;
- if(i>=1)
- {
- if((l<=n && arr[l]>arr[i])||(r<=n && arr[r]>arr[i]))
- {
- c = 0;
- }
- else
- {
- check(arr,i-1,n);
- }
- }
- }
- };
- int main()
- {
- Heap obj;
- freopen("input.txt","r",stdin);
- int arr[100];
- while(cin)
- {
- cin>>arr[length++];
- }
- length -= 2;
- for(int i = 1;i<= length;i++)
- cout<<arr[i]<<" ";
- cout<<endl<<endl;
- obj.Build_MaxHeap(arr);
- cout<<"Max Heap:"<<endl;
- for(int i = 1;i<= length;i++)
- cout<<arr[i]<<" ";
- cout<<endl<<endl;
- cout<<"Min Heap:"<<endl;
- obj.Build_MinHeap(arr);
- for(int i = 1;i<= length;i++)
- cout<<arr[i]<<" ";
- cout<<endl<<endl;
- cout<<"After Sorting:"<<endl;
- obj.Heap_Sort(arr,length);
- for(int i = 1;i<= length;i++)
- cout<<arr[i]<<" ";
- cout<<endl<<endl;
- obj.check(arr,length/2,length);
- if(c)
- cout<<"MAX HEAP"<<endl<<endl;
- else
- cout<<"Not MAX HEAP"<<endl<<endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment