Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- class Heap
- {
- std::vector<int> h;
- std::vector<int> ID_to_HeapIdx;
- int heap_size;
- int curr_ID;
- public:
- Heap();
- void siftup(int ID,std::vector<int>& HeapIdx_to_ID);
- void siftdown(int ID,std::vector<int>& HeapIdx_to_ID);
- void add(int vertex,int ID,std::vector<int>& HeapIdx_to_ID);
- void delete_vertex(int ID,std::vector<int>& HeapIdx_to_ID);
- bool isempty();
- void out();
- int get_root();
- };
- Heap::Heap()
- {
- std::vector<int> h;
- heap_size = 0;
- curr_ID = 0;
- std::vector<int> ID_to_HeapIdx;
- }
- int Heap::get_root()
- {
- if (heap_size > 0)
- return h[0];
- return -1;
- }
- bool Heap::isempty()
- {
- if (heap_size == 0)
- return true;
- return false;
- }
- void Heap::siftup(int ID, std::vector<int>& HeapIdx_to_ID)
- {
- int curr, parent,tmp;
- curr = heap_size - 1;
- parent = (curr - 1) ;
- for (int i = 0; i < HeapIdx_to_ID.size(); i++)
- for (int i = 0; i < ID_to_HeapIdx.size(); i++)
- while (parent >= 0 && curr > 0)
- {
- if (h[parent] < h[curr])
- {
- int buff = h[curr];
- h[curr] = h[parent];
- h[parent] = buff;
- tmp = HeapIdx_to_ID[parent];
- HeapIdx_to_ID[parent] = HeapIdx_to_ID[curr];
- HeapIdx_to_ID[curr] = tmp;
- tmp = ID_to_HeapIdx[HeapIdx_to_ID[parent]];
- ID_to_HeapIdx[HeapIdx_to_ID[parent]] = ID_to_HeapIdx[HeapIdx_to_ID[curr]];
- ID_to_HeapIdx[HeapIdx_to_ID[curr]] = tmp;
- }
- curr = parent;
- parent = (curr - 1) ;
- }
- }
- void Heap::add(int vertex, int ID, std::vector<int>& HeapIdx_to_ID)
- {
- h.push_back(vertex);
- ID_to_HeapIdx.push_back(heap_size);
- HeapIdx_to_ID.push_back(ID);
- heap_size++;
- siftup(ID, HeapIdx_to_ID);
- }
- void Heap::siftdown(int ID,std::vector<int>& HeapIdx_to_ID)
- {
- int parent, max_child,tmp,buff;
- int curr = ID_to_HeapIdx[ID];
- int child_l = 2 * curr + 1;
- int child_r = 2 * curr + 2;
- if (h[child_r] < h[child_l])
- max_child = child_l;
- else
- max_child = child_r;
- while (child_l < heap_size)
- {
- if (child_l == heap_size - 1)
- max_child = child_l;
- else if (h[child_r] < h[child_l])
- max_child = child_l;
- else
- max_child = child_r;
- if (h[curr] < h[max_child])
- {
- buff = h[curr];
- h[curr] = h[max_child];
- h[max_child] = buff;
- tmp = HeapIdx_to_ID[max_child];
- HeapIdx_to_ID[max_child] = HeapIdx_to_ID[curr];
- HeapIdx_to_ID[curr] = tmp;
- tmp = ID_to_HeapIdx[HeapIdx_to_ID[max_child]];
- ID_to_HeapIdx[HeapIdx_to_ID[max_child]] = ID_to_HeapIdx[HeapIdx_to_ID[curr]];
- ID_to_HeapIdx[HeapIdx_to_ID[curr]] = tmp;
- }
- curr = max_child;
- child_l = 2 * curr + 1;
- child_r = 2 * curr + 2;
- }
- }
- void Heap::delete_vertex(int ID, std::vector<int>& HeapIdx_to_ID)
- {
- int pos = ID_to_HeapIdx[ID];
- h[pos] = h[heap_size - 1];
- h.pop_back();
- heap_size--;
- siftdown(ID, HeapIdx_to_ID);
- }
- void Heap::out(void)
- {
- for (int i = 0; i < heap_size; i++)
- {
- cout << h[i] << " ";
- }
- cout << endl;
- }
- int main()
- {
- /*
- void siftup(int ID,std::vector<int>& HeapIdx_to_ID);
- void siftdown(int ID,std::vector<int>& HeapIdx_to_ID);
- void add(int vertex,int ID,std::vector<int>& HeapIdx_to_ID);
- void delete_vertex(int ID,std::vector<int>& HeapIdx_to_ID);
- bool isempty();
- void out();
- int* get_root();
- */
- int ID = -1;
- std::vector<int> HeapIdx_to_ID;
- Heap heap;
- //ID++;
- cout << "--------" << endl;
- ID++;
- heap.add(1,ID,HeapIdx_to_ID);
- cout << "heap: ";
- heap.out();
- cout << "root" << heap.get_root() << endl;
- cout << HeapIdx_to_ID.size() << endl;
- cout << "--------" << endl;
- cout << "root" << heap.get_root() << endl;
- ID++;
- heap.add(3,ID,HeapIdx_to_ID);
- cout << "heap: ";
- heap.out();
- cout << "root" << heap.get_root() << endl;
- cout << HeapIdx_to_ID.size() << endl;
- cout << "--------" << endl;
- ID++;
- heap.add(2,ID,HeapIdx_to_ID);
- cout << "heap: ";
- heap.out();
- cout << "root" << heap.get_root() << endl;
- cout << "--------" << endl;
- cout << "de \n";
- heap.delete_vertex(2,HeapIdx_to_ID);
- heap.out();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment