Advertisement
STANAANDREY

max heap

Oct 29th, 2019
274
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector <int> h;
  5.  
  6. inline bool cmpH(vector <int>& heap,int ind1, int ind2)
  7. {
  8.     return (heap[ind1] > heap[ind2]);//heap type
  9. }
  10.  
  11. int siftUp(vector<int>& heap, int index)
  12. {
  13.     while (index > 1 && cmpH(heap, index, index / 2))
  14.     {
  15.         swap(heap[index], heap[index / 2]);
  16.         index /= 2;
  17.     }
  18.     return index;
  19. }
  20.  
  21. int siftDown(vector<int>& heap, int index)
  22. {
  23.     while (2 * index < (int)heap.size())
  24.     {
  25.         int child = 2 * index;
  26.         if (child + 1 < (int)heap.size() && cmpH(heap, child + 1, child))
  27.         {
  28.             child += 1;
  29.         }
  30.         if (cmpH(heap, child, index))
  31.         {
  32.             swap(heap[child], heap[index]);
  33.             index = child;
  34.         }
  35.         else
  36.         {
  37.             return index;
  38.         }
  39.     }
  40.     return index;
  41. }
  42.  
  43. int peek(vector<int>& heap)
  44. {
  45.     return heap[1];
  46. }
  47.  
  48. void insertinheap(vector<int>& heap, int key)
  49. {
  50.     heap.push_back(key);
  51.     siftUp(heap, (int)heap.size() - 1);
  52. }
  53.  
  54. int pop(vector<int>& heap)
  55. {
  56.     int key = heap[1];
  57.     swap(heap[1], heap.back());
  58.     heap.pop_back();
  59.     siftDown(heap, 1);
  60.     return key;
  61. }
  62.  
  63. int main()
  64. {
  65.     insertinheap(h,22);
  66.     insertinheap(h,102);
  67.     insertinheap(h,99);
  68.     insertinheap(h,10);
  69.     insertinheap(h,10000);
  70.     insertinheap(h,11);
  71.     cout << peek(h) << endl;//10000
  72.     pop(h);
  73.     cout << peek(h) << endl;//102
  74.     return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement