Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector <int> h;
- inline bool cmpH(vector <int>& heap,int ind1, int ind2)
- {
- return (heap[ind1] > heap[ind2]);//heap type
- }
- int siftUp(vector<int>& heap, int index)
- {
- while (index > 1 && cmpH(heap, index, index / 2))
- {
- swap(heap[index], heap[index / 2]);
- index /= 2;
- }
- return index;
- }
- int siftDown(vector<int>& heap, int index)
- {
- while (2 * index < (int)heap.size())
- {
- int child = 2 * index;
- if (child + 1 < (int)heap.size() && cmpH(heap, child + 1, child))
- {
- child += 1;
- }
- if (cmpH(heap, child, index))
- {
- swap(heap[child], heap[index]);
- index = child;
- }
- else
- {
- return index;
- }
- }
- return index;
- }
- int peek(vector<int>& heap)
- {
- return heap[1];
- }
- void insertinheap(vector<int>& heap, int key)
- {
- heap.push_back(key);
- siftUp(heap, (int)heap.size() - 1);
- }
- int pop(vector<int>& heap)
- {
- int key = heap[1];
- swap(heap[1], heap.back());
- heap.pop_back();
- siftDown(heap, 1);
- return key;
- }
- int main()
- {
- insertinheap(h,22);
- insertinheap(h,102);
- insertinheap(h,99);
- insertinheap(h,10);
- insertinheap(h,10000);
- insertinheap(h,11);
- cout << peek(h) << endl;//10000
- pop(h);
- cout << peek(h) << endl;//102
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement