shabbyheart

Max Heap,MIn heap,sort,check max heap or not

Jan 31st, 2020
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int length = 1 ,c = 1;
  5.  
  6. class Heap
  7. {
  8. public:
  9.     Build_MaxHeap(int arr[])
  10.     {
  11.         int n = length;
  12.         for(int i=n/2;i>=1;i--)
  13.             Max_heapify(arr,i,n);
  14.     }
  15.  
  16.     Max_heapify(int arr[],int i,int n)
  17.     {
  18.         int leftchild = 2*i;
  19.         int rightchild = 2*i+1;
  20.         int largest;
  21.  
  22.         if(leftchild<=n && arr[leftchild]>arr[i])
  23.             largest = leftchild;
  24.         else
  25.             largest = i;
  26.  
  27.         if(rightchild <=n && arr[rightchild]>arr[largest])
  28.             largest = rightchild;
  29.  
  30.         if(largest != i)
  31.         {
  32.             swap(arr[largest],arr[i]);
  33.             Max_heapify(arr,largest,n);
  34.  
  35.         }
  36.  
  37.     }
  38.  
  39.     Build_MinHeap(int arr[])
  40.     {
  41.         int n = length;
  42.         for(int i=n/2;i>=1;i--)
  43.             Min_heapify(arr,i,n);
  44.     }
  45.  
  46.     Min_heapify(int arr[],int i,int n)
  47.     {
  48.         int leftchild = 2*i;
  49.         int rightchild = 2*i+1;
  50.         int smaller;
  51.  
  52.         if(leftchild<=n && arr[leftchild]<arr[i])
  53.             smaller = leftchild;
  54.         else
  55.             smaller = i;
  56.  
  57.         if(rightchild <=n && arr[rightchild]<arr[smaller])
  58.             smaller = rightchild;
  59.  
  60.         if(smaller != i)
  61.         {
  62.             swap(arr[smaller],arr[i]);
  63.             Min_heapify(arr,smaller,n);
  64.  
  65.         }
  66.  
  67.     }
  68.  
  69.     Heap_Sort(int arr[],int n)
  70.     {
  71.         Build_MaxHeap(arr);      ///For Sorting First Built Max Heap
  72.         for(int i = 0;i<n;i++)
  73.         {
  74.  
  75.             swap(arr[1],arr[n-i]);  /// Swap 1st and last element of Max heap since 1st element is the MAX element
  76.             Max_heapify(arr,1,n-i-1);  /// call Max_heapify without last element and again 1st element will be the MAX element
  77.         }
  78.     }
  79.  
  80.  
  81.     void check(int arr[],int i,int n)
  82.     {
  83.         int l = 2*i;
  84.         int r = 2*i+1;
  85.  
  86.        if(i>=1)
  87.        {
  88.             if((l<=n && arr[l]>arr[i])||(r<=n && arr[r]>arr[i]))
  89.             {
  90.               c = 0;
  91.             }
  92.             else
  93.             {
  94.                 check(arr,i-1,n);
  95.             }
  96.        }
  97.  
  98.     }
  99.  
  100.  
  101.  
  102.  
  103. };
  104.  
  105.  
  106.  
  107.  
  108. int main()
  109. {
  110.     Heap obj;
  111.     freopen("input.txt","r",stdin);
  112.     int arr[100];
  113.     while(cin)
  114.     {
  115.         cin>>arr[length++];
  116.     }
  117.  
  118.     length -= 2;
  119.  
  120.     for(int i = 1;i<= length;i++)
  121.         cout<<arr[i]<<" ";
  122.     cout<<endl<<endl;
  123.  
  124.  
  125.     obj.Build_MaxHeap(arr);
  126.     cout<<"Max Heap:"<<endl;
  127.     for(int i = 1;i<= length;i++)
  128.         cout<<arr[i]<<" ";
  129.     cout<<endl<<endl;
  130.  
  131.     cout<<"Min Heap:"<<endl;
  132.     obj.Build_MinHeap(arr);
  133.     for(int i = 1;i<= length;i++)
  134.         cout<<arr[i]<<" ";
  135.     cout<<endl<<endl;
  136.  
  137.     cout<<"After Sorting:"<<endl;
  138.     obj.Heap_Sort(arr,length);
  139.     for(int i = 1;i<= length;i++)
  140.         cout<<arr[i]<<" ";
  141.     cout<<endl<<endl;
  142.  
  143.     obj.check(arr,length/2,length);
  144.     if(c)
  145.         cout<<"MAX HEAP"<<endl<<endl;
  146.     else
  147.         cout<<"Not MAX HEAP"<<endl<<endl;
  148.  
  149.     return 0;
  150. }
Add Comment
Please, Sign In to add comment