peltorator

Dijkstra Heap

Apr 11th, 2019
155
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. const int N = 100005;
  3.  
  4. template<typename T> // max path type
  5. class Heap
  6. {
  7. public:
  8.     int vec[N], pos[N];
  9.     T val[N];
  10.     int siz;
  11.  
  12.     Heap() //number of vertexes
  13.     {
  14.         siz = 0;
  15.         for (int i = 0; i < N; i++)
  16.             pos[i] = -1;
  17.     }
  18.  
  19.     void siftDown(int v)
  20.     {
  21.         while (true)
  22.         {
  23.             int u = (v << 1) | 1;
  24.             if (u + 1 < siz && val[vec[u + 1]] < val[vec[u]])
  25.                 ++u;
  26.             if (u < siz && val[vec[u]] < val[vec[v]])
  27.             {
  28.                 swap(pos[vec[u]], pos[vec[v]]);
  29.                 swap(vec[u], vec[v]);
  30.                 v = u;
  31.             }
  32.             else
  33.                 break;
  34.         }
  35.     }
  36.  
  37.     void siftUp(int v)
  38.     {
  39.         while (v)
  40.         {
  41.             int u = ((v - 1) >> 1);
  42.             if (val[vec[u]] > val[vec[v]])
  43.             {
  44.                 swap(pos[vec[u]], pos[vec[v]]);
  45.                 swap(vec[u], vec[v]);
  46.                 v = u;
  47.             }
  48.             else
  49.                 break;
  50.         }
  51.     }
  52.  
  53.     Heap(vector<T> a)
  54.     {
  55.         vec = a;
  56.         for (int i = siz - 1; i >= 0; i--)
  57.             siftDown(i);
  58.     }
  59.  
  60.     T best_vertex()
  61.     {
  62.         return vec[0];
  63.     }
  64.  
  65.     void push(int v, T value)
  66.     {
  67.         if (pos[v] == -1)
  68.         {
  69.             vec[siz++] = v;
  70.             pos[v] = siz - 1;
  71.         }
  72.         val[v] = value;
  73.         siftUp(pos[v]);
  74.     }
  75.  
  76.     void pop()
  77.     {
  78.         swap(vec[0], vec[siz - 1]);
  79.         swap(pos[vec[0]], pos[vec[siz - 1]]);
  80.         pos[vec[siz - 1]] = -1;
  81.         siz--;
  82.         siftDown(0);
  83.     }
  84.  
  85.     int size()
  86.     {
  87.         return siz;
  88.     }
  89. };
RAW Paste Data