Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- template<typename T>
- class Heap
- {
- public:
- vector<T> vec;
- Heap()
- {
- vec.clear();
- }
- void siftDown(int v)
- {
- while (true)
- {
- int u = (v << 1) | 1;
- if (u + 1 < sz(vec) && vec[u + 1] < vec[u])
- ++u;
- if (u < sz(vec) && vec[u] < vec[v])
- swap(vec[u], vec[v]), v = u;
- else
- break;
- }
- }
- void siftUp(int v)
- {
- while (v)
- {
- int u = ((v - 1) >> 1);
- if (vec[u] > vec[v])
- swap(vec[u], vec[v]), v = u;
- else
- break;
- }
- }
- Heap(vector<T> a)
- {
- vec = a;
- for (int i = sz(vec) - 1; i >= 0; i--)
- siftDown(i);
- }
- T min()
- {
- return vec[0];
- }
- void push(T val)
- {
- vec.push_back(val);
- siftUp(sz(vec) - 1);
- }
- void pop()
- {
- swap(vec[0], vec.back());
- vec.pop_back();
- siftDown(0);
- }
- int size()
- {
- return vec.size();
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement