Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- include "heap.h"
- Heap::Heap(vector<int>& vec)
- {
- h = vec;
- for(int i = (int)h.size()/2; i >=0; i--)
- {
- correct(i);
- }
- }
- void Heap::add(int value)
- {
- h.push_back(value);
- int current_index = h.size() - 1;
- int parent = (current_index - 1)/2;
- while(h[current_index] > h[parent])
- {
- swap(h[current_index], h[parent]);
- current_index = parent;
- parent = (parent - 1)/2;
- }
- }
- void Heap::pop()
- {
- std::swap(h[0], h[h.size()-1]);
- h.erase(h.begin() + h.size()-1);
- correct(0);
- }
- void Heap::print()
- {
- for(int i = 0; i < h.size(); i++)
- {
- cout << h[i] << " ";
- }
- cout << endl;
- }
- void Heap::correct(int index)
- {
- unsigned left_index,right_index,biggest_child;
- while(1)
- {
- left_index=2*index+1;
- right_index=2*index+2;
- biggest_child=index;
- if(left_index<h.size()&&h[left_index]>h[biggest_child])
- {
- biggest_child=left_index;
- }
- if(right_index<h.size()&&h[right_index]>h[biggest_child])
- {
- biggest_child=right_index;
- }
- if(biggest_child==index)
- break;
- swap(h[index],h[biggest_child]);
- index=biggest_child;
- }
- }
- void Heap::increase(int index, int change)
- {
- if(index >= h.size() || index < 0 || change < 0)
- {
- throw exception();
- }
- h[index] += change;
- int current_index = index;
- int parent = (current_index - 1)/2;
- while(h[current_index] > h[parent])
- {
- swap(h[current_index], h[parent]);
- current_index = parent;
- parent = (parent - 1)/2;
- }
- }
- void Heap::decrement(int index, int change)
- {
- if(index >= h.size() || index < 0 || change < 0)
- {
- throw exception();
- }
- h[index] -= change;
- correct(index);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement