peltorator

heap template

Apr 11th, 2019
146
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. template<typename T>
  3. class Heap
  4. {
  5. public:
  6.     vector<T> vec;
  7.  
  8.     Heap()
  9.     {
  10.         vec.clear();
  11.     }
  12.  
  13.     void siftDown(int v)
  14.     {
  15.         while (true)
  16.         {
  17.             int u = (v << 1) | 1;
  18.             if (u + 1 < sz(vec) && vec[u + 1] < vec[u])
  19.                 ++u;
  20.             if (u < sz(vec) && vec[u] < vec[v])
  21.                 swap(vec[u], vec[v]), v = u;
  22.             else
  23.                 break;
  24.         }
  25.     }
  26.  
  27.     void siftUp(int v)
  28.     {
  29.         while (v)
  30.         {
  31.             int u = ((v - 1) >> 1);
  32.             if (vec[u] > vec[v])
  33.                 swap(vec[u], vec[v]), v = u;
  34.             else
  35.                 break;
  36.         }
  37.     }
  38.  
  39.     Heap(vector<T> a)
  40.     {
  41.         vec = a;
  42.         for (int i = sz(vec) - 1; i >= 0; i--)
  43.             siftDown(i);
  44.     }
  45.  
  46.     T min()
  47.     {
  48.         return vec[0];
  49.     }
  50.  
  51.     void push(T val)
  52.     {
  53.         vec.push_back(val);
  54.         siftUp(sz(vec) - 1);
  55.     }
  56.  
  57.     void pop()
  58.     {
  59.         swap(vec[0], vec.back());
  60.         vec.pop_back();
  61.         siftDown(0);
  62.     }
  63.  
  64.     int size()
  65.     {
  66.         return vec.size();
  67.     }
  68. };
RAW Paste Data