SHARE
TWEET

Untitled

a guest Jun 12th, 2019 60 in 15 hours
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <limits>
  3.  
  4. using namespace std;
  5.  
  6.  
  7. void heapSort(int arr[], int n, int root)
  8. {
  9.     int largest = root;
  10.     int left = 2 * root + 1;
  11.     int right = 2 * root + 2;
  12.  
  13.     if (left < n && arr[left] > arr[largest])
  14.         largest = left;
  15.  
  16.     if (right < n && arr[right] > arr[largest])
  17.         largest = right;
  18.  
  19.     if (largest != root)
  20.     {
  21.         swap(arr[root], arr[largest]);
  22.         heapSort(arr, n, largest);
  23.     }
  24. }
  25.  
  26. void heapify(int arr[], int n)
  27. {
  28.     for (int i = n / 2 - 1; i >= 0; i--)
  29.         heapSort(arr, n, i);
  30. }
  31.  
  32. class heap
  33. {
  34.  
  35. private:
  36.     int* arr;
  37.     int size;
  38.     int capacity;
  39.  
  40.     void resize()
  41.     {
  42.         capacity = capacity* 2;
  43.         int * newArr = new int[capacity];
  44.  
  45.         for (int i = 0; i< size; ++i)
  46.         {
  47.             newArr[i] = arr[i];
  48.  
  49.         }
  50.         delete[]arr;
  51.         arr = newArr;
  52.     }
  53.  
  54. public:
  55.  
  56.     heap()
  57.     {
  58.         capacity = 7;
  59.         size = 0;
  60.         arr = new int[capacity];
  61.     }
  62.     heap(const heap& other) = delete;
  63.     heap& operator= (const heap& other) = delete;
  64.     ~heap()
  65.     {
  66.         delete[] arr;
  67.     }
  68.  
  69.  
  70.     int top() const
  71.     {
  72.         if (size == 0) {
  73.             cout << "Queue empty.\n";
  74.             return 0;
  75.         }
  76.         else
  77.             return arr[0];
  78.     }
  79.  
  80.     void insert(int element)
  81.     {
  82.         if (size == capacity) {
  83.             resize();
  84.         }
  85.         arr[size] = element;
  86.         ++size;
  87.         heapify(arr, size);
  88.     }
  89.  
  90.     int popTop()
  91.     {
  92.         if (size == 0) {
  93.             cout << "Queue empty.\n";
  94.             return 0;
  95.         }
  96.         int toReturn = arr[0];
  97.         swap(arr[0], arr[size-1]);
  98.         --size;
  99.         heapSort(arr, size, 0);
  100.         return toReturn;
  101.     }
  102. };
  103.  
  104. int main()
  105. {
  106.     int number; long int newnum;
  107.     heap hp;
  108.     do {
  109.  
  110.         cout << " To insert press 1.\n";
  111.         cout << " To see the top press 2.\n";
  112.         cout << " To pop the top press 3.\n";
  113.         cout << " To exit press 4.\n";
  114.         cout << " Choose (1-4): ";
  115.         cin >> number;
  116.         cout << '\n';
  117.  
  118.  
  119.         switch (number) {
  120.  
  121.         case 1:
  122.             cout << " Write the element you want to insert: ";
  123.  
  124.  
  125.             bool fail;
  126.             do{
  127.  
  128.                 cin>> newnum;
  129.                 fail= cin.fail();
  130.                 cin.clear();
  131.                 if (fail != true) break;
  132.                 cin.ignore(numeric_limits<streamsize>:: max(), '\n');
  133.                 cout << " Invalid input, write a number to insert:    ";
  134.             }while (fail == true);
  135.  
  136.             hp.insert(newnum);
  137.             break;
  138.  
  139.  
  140.         case 2:
  141.             cout << "\nThe top is:" << hp.top() << "\n";
  142.             break;
  143.  
  144.         case 3:
  145.             cout << "  \n " << hp.popTop() << " was popped from the queue.\n";
  146.             break;
  147.  
  148.         case 4:
  149.             break;
  150.  
  151.         default:
  152.             cout << "Wrong operation. Please enter a number from 1 to 4 \n";
  153.             break;
  154.  
  155.         }
  156.         cout << "\n";
  157.     } while (number != 4);
  158.  
  159.     return 0;
  160. }
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