SHARE
TWEET

Untitled

a guest Jul 18th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #define  INFINITY 99999999
  3. using namespace std;
  4.  
  5. void swap(int *a, int *b)
  6. {
  7.     int temp = *a;
  8.     *a = *b;
  9.     *b = temp;
  10. }
  11. class MaxPq{
  12.     int initSize;
  13.     int MaxSize;
  14.     int *arr;
  15.     int length;
  16.  
  17.  
  18. public:
  19.     MaxPq();
  20.  
  21.  
  22.     void Insert(int x);
  23.     int FindMax();
  24.     int ExtractMax();
  25.     void IncreaseKey(int i, int newKey);
  26.     void DecreaseKey(int i, int newKey);
  27.     void Print();
  28.  
  29.  
  30.     int FindElement(int n);
  31.     void Heapify(int i);
  32.     int getRight(int i);
  33.     int getLeft(int i);
  34.     int getParent(int i);
  35. };
  36.  
  37. int main()
  38. {
  39.     int choice;
  40.     MaxPq q;
  41.  
  42.     while(1){
  43.         cout<<"1. Insert"<<endl;
  44.         cout<<"2. Find Max"<<endl;
  45.         cout<<"3. Extract Max"<<endl;
  46.         cout<<"4. Increase Key"<<endl;
  47.         cout<<"5. Decrease Key"<<endl;
  48.         cout<<"6. Print"<<endl;
  49.         cout<<"7. Quit"<<endl;
  50.         cout<<"Enter Your Choice"<<endl;
  51.         cin>>choice;
  52.         if(choice==1){
  53.             int n;
  54.             cout<<"Enter the number"<<endl;
  55.             cin>>n;
  56.             q.Insert(n);
  57.         }
  58.         else if (choice==2){
  59.             int max = q.FindMax();
  60.             cout<<"Max Element is: "<<max<<endl;
  61.         }
  62.         else if(choice==3){
  63.             int max = q.ExtractMax();
  64.             cout<<"Max = "<<max<<endl;
  65.             cout<<"Max Extracted"<<endl;
  66.         }
  67.         else if (choice == 4){
  68.             int i , key;
  69.             cout<<"Enter Position"<<endl;
  70.             int n = q.FindElement(i);
  71.             cout<<"Element in "<<i<<"th position is "<<n<<endl;
  72.             cout<<"Enter new value : ";
  73.             cin>>key;
  74.             q.IncreaseKey(i, key);
  75.             //q.Heapify(i);
  76.         }
  77.         else if (choice == 5){
  78.             int i , key;
  79.             cout<<"Enter Position"<<endl;
  80.             int n = q.FindElement(i);
  81.             cout<<"Element in "<<i<<"th position is "<<n<<endl;
  82.             cout<<"Enter new value : ";
  83.             cin>>key;
  84.             q.DecreaseKey(i, key);
  85.             //q.Heapify();
  86.         }
  87.         else if(choice == 6){
  88.             cout<<"The Queue is"<<endl;
  89.             q.Print();
  90.         }
  91.         else if(choice == 7){
  92.             cout<<"Quiting program"<<endl;
  93.             break;
  94.         }
  95.     }
  96. }
  97.  
  98.  
  99. MaxPq::MaxPq() {
  100.     initSize = 10;
  101.     MaxSize = initSize;
  102.     arr = new int[MaxSize];
  103.     length = 0;
  104.  
  105. }
  106.  
  107. void MaxPq::Insert(int x) {
  108.     if (length >= MaxSize ){
  109.         arr = (int*) realloc(arr, sizeof(int)*(MaxSize+10));
  110.         MaxSize = MaxSize+10;
  111.         length = length+1;
  112.         arr[length] = -INFINITY;
  113.         IncreaseKey(length, x);
  114.     }
  115.     else{
  116.         length = length+1;
  117.         arr[length] = -INFINITY;
  118.         IncreaseKey(length, x);
  119.  
  120.     }
  121.  
  122. }
  123.  
  124. int MaxPq::ExtractMax() {
  125.     int max = arr[1];
  126.     arr[1] = arr[length];
  127.     length--;
  128.     Heapify(1);
  129.     return max;
  130. }
  131.  
  132. int MaxPq::FindMax() {
  133.     return arr[1];
  134. }
  135.  
  136. void MaxPq::IncreaseKey(int i, int newKey) {
  137.     arr[i] = newKey;
  138.     while (i>1 && arr[getParent(i)]<arr[i]){
  139.         swap(arr[i],arr[getParent(i)]);
  140.         i = getParent(i);
  141.     }
  142.  
  143. }
  144.  
  145. void MaxPq::DecreaseKey(int i, int newKey) {
  146.     arr[i] = newKey;
  147.     Heapify(i);
  148.  
  149. }
  150.  
  151. void MaxPq::Print() {
  152.     for (int i = 1; i <=length ; i++) {
  153.         cout<<arr[i]<<" ";
  154.     }
  155.     cout<<endl;
  156.  
  157. }
  158.  
  159. int MaxPq::FindElement(int n) {
  160.     for (int i = 1; i <=length ; ++i) {
  161.         if (arr[i]==n)
  162.             return i;
  163.     }
  164.     return -1;
  165. }
  166.  
  167. void MaxPq::Heapify(int i) {
  168.     int largest = i;
  169.     int left = getLeft(i);
  170.     int right = getRight(i);
  171.  
  172.     if (left <= length && left>0){
  173.         if (arr[left]>arr[i]){
  174.             largest = left;
  175.         }
  176.     }
  177.     if (right<=length && right>0){
  178.         if(arr[right]>arr[largest]){
  179.             largest = right;
  180.         }
  181.     }
  182.  
  183.     if (largest != i){
  184.         swap(&arr[i],&arr[largest]);
  185.         Heapify(largest);
  186.     }
  187.  
  188. }
  189.  
  190. int MaxPq::getParent(int i) {
  191.     if(i> 1 && i<length)
  192.         return i/2;
  193.     return -1;
  194. }
  195.  
  196. int MaxPq::getRight(int i) {
  197.     if(((2*i)+1)<length && i>=1)
  198.         return (2*i)+1;
  199.     return -1;
  200. }
  201.  
  202. int MaxPq::getLeft(int i) {
  203.     if((2*i)<length && i>=1)
  204.         return 2*i;
  205.     return 0;
  206. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top