Advertisement
shabbyheart

lab 4 algorithm

Nov 24th, 2019
283
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.63 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int length = 1 ;
  5.  
  6. class Heap
  7. {
  8. public:
  9.  
  10.     Build_MinHeap(int arr[])
  11.     {
  12.         int n = length;
  13.         for(int i=n/2;i>=1;i--)
  14.             Min_heapify(arr,i,n);
  15.     }
  16.  
  17.     Min_heapify(int arr[],int i,int n)
  18.     {
  19.         int leftchild = 2*i;
  20.         int rightchild = 2*i+1;
  21.         int smaller;
  22.  
  23.         if(leftchild<=n && arr[leftchild]<arr[i])
  24.             smaller = leftchild;
  25.         else
  26.             smaller = i;
  27.  
  28.         if(rightchild <=n && arr[rightchild]<arr[smaller])
  29.             smaller = rightchild;
  30.  
  31.         if(smaller != i)
  32.         {
  33.             swap(arr[smaller],arr[i]);
  34.             Min_heapify(arr,smaller,n);
  35.  
  36.         }
  37.  
  38.     }
  39.     void min_heap_insert(int arr[],int key,int n)
  40.     {
  41.         length = n+1;
  42.         arr[n+1] = key;
  43.  
  44.         heap_change_key(arr,11,key);
  45.     }
  46.     void heap_change_key(int arr[],int i,int key)
  47.     {
  48.  
  49.         while((i > 1) && arr[i/2] > arr[i])
  50.         {
  51.             swap(arr[i],arr[i/2]);
  52.             i = i/2;
  53.         }
  54.     }
  55.     void display( int arr[])
  56.     {
  57.         for(int i = 1;i<= length;i++)
  58.             cout<<arr[i]<<" ";
  59.         cout<<endl<<endl;
  60.     }
  61.  
  62.  
  63.  
  64.  
  65. };
  66.  
  67.  
  68.  
  69.  
  70. int main()
  71. {
  72.     Heap obj;
  73.     freopen("input.txt","r",stdin);
  74.     int arr[100];
  75.     int key;
  76.     cin>>key;
  77.     while(cin)
  78.     {
  79.         cin>>arr[length++];
  80.     }
  81.  
  82.     length -= 2;
  83.  
  84.  
  85.  
  86.     cout<<"Original Min Heap:"<<endl;
  87.     obj.Build_MinHeap(arr);
  88.     obj.display(arr);
  89.  
  90.     cout<<"After Insert a value: "<<endl;
  91.     obj.min_heap_insert(arr,key,length);
  92.     obj.display(arr);
  93.  
  94.  
  95.     return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement