vadimk772336

Handle Без cout

Oct 30th, 2021
1,553
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. class Heap
  7. {
  8.     std::vector<int> h;
  9.     std::vector<int> ID_to_HeapIdx;
  10.     int heap_size;
  11.     int curr_ID;
  12.  
  13. public:
  14.     Heap();
  15.     void siftup(int ID,std::vector<int>& HeapIdx_to_ID);
  16.     void siftdown(int ID,std::vector<int>& HeapIdx_to_ID);
  17.     void add(int vertex,int ID,std::vector<int>& HeapIdx_to_ID);
  18.     void delete_vertex(int ID,std::vector<int>& HeapIdx_to_ID);
  19.     bool isempty();
  20.     void out();
  21.     int get_root();
  22. };
  23.  
  24. Heap::Heap()
  25. {
  26.     std::vector<int> h;
  27.     heap_size = 0;
  28.     curr_ID = 0;
  29.     std::vector<int> ID_to_HeapIdx;
  30. }
  31.  
  32. int Heap::get_root()
  33. {
  34.     if (heap_size > 0)
  35.         return h[0];
  36.     return -1;
  37. }
  38.  
  39. bool Heap::isempty()
  40. {
  41.     if (heap_size == 0)
  42.         return true;
  43.     return false;
  44. }
  45.  
  46. void Heap::siftup(int ID, std::vector<int>& HeapIdx_to_ID)
  47. {
  48.     int curr, parent,tmp;
  49.     curr = heap_size - 1;
  50.     parent = (curr - 1) ;
  51.     for (int i = 0; i < HeapIdx_to_ID.size(); i++)
  52.    
  53.     for (int i = 0; i < ID_to_HeapIdx.size(); i++)
  54.    
  55.     while (parent >= 0 && curr > 0)
  56.     {
  57.        
  58.         if (h[parent] < h[curr])
  59.         {
  60.  
  61.             int buff = h[curr];
  62.             h[curr] = h[parent];
  63.             h[parent] = buff;
  64.  
  65.             tmp = HeapIdx_to_ID[parent];    
  66.             HeapIdx_to_ID[parent] = HeapIdx_to_ID[curr];  
  67.             HeapIdx_to_ID[curr] = tmp;
  68.  
  69.      
  70.             tmp = ID_to_HeapIdx[HeapIdx_to_ID[parent]];
  71.             ID_to_HeapIdx[HeapIdx_to_ID[parent]] = ID_to_HeapIdx[HeapIdx_to_ID[curr]];
  72.             ID_to_HeapIdx[HeapIdx_to_ID[curr]] = tmp;
  73.  
  74.         }
  75.         curr = parent;
  76.         parent = (curr - 1) ;
  77.     }
  78.    
  79. }
  80.  
  81. void Heap::add(int vertex, int ID, std::vector<int>& HeapIdx_to_ID)
  82. {
  83.  
  84.     h.push_back(vertex);
  85.     ID_to_HeapIdx.push_back(heap_size);
  86.     HeapIdx_to_ID.push_back(ID);
  87.     heap_size++;
  88.     siftup(ID, HeapIdx_to_ID);
  89. }
  90.  
  91. void Heap::siftdown(int ID,std::vector<int>& HeapIdx_to_ID)
  92. {
  93.     int parent, max_child,tmp,buff;
  94.  
  95.     int curr = ID_to_HeapIdx[ID];
  96.     int child_l = 2 * curr + 1;
  97.     int child_r = 2 * curr + 2;
  98.      
  99.     if (h[child_r] < h[child_l])
  100.         max_child = child_l;
  101.     else
  102.         max_child = child_r;
  103.  
  104.     while (child_l < heap_size)
  105.     {
  106.         if (child_l == heap_size - 1)
  107.             max_child = child_l;
  108.         else if (h[child_r] < h[child_l])
  109.             max_child = child_l;
  110.         else
  111.             max_child = child_r;
  112.  
  113.         if (h[curr] < h[max_child])
  114.         {
  115.  
  116.             buff = h[curr];
  117.             h[curr] = h[max_child];
  118.             h[max_child] = buff;
  119.  
  120.             tmp = HeapIdx_to_ID[max_child];
  121.             HeapIdx_to_ID[max_child] = HeapIdx_to_ID[curr];
  122.             HeapIdx_to_ID[curr] = tmp;
  123.  
  124.             tmp = ID_to_HeapIdx[HeapIdx_to_ID[max_child]];
  125.             ID_to_HeapIdx[HeapIdx_to_ID[max_child]] = ID_to_HeapIdx[HeapIdx_to_ID[curr]];
  126.             ID_to_HeapIdx[HeapIdx_to_ID[curr]] = tmp;
  127.         }
  128.         curr = max_child;
  129.         child_l = 2 * curr + 1;
  130.         child_r = 2 * curr + 2;
  131.     }
  132. }
  133.  
  134.  
  135.  
  136. void Heap::delete_vertex(int ID, std::vector<int>& HeapIdx_to_ID)
  137. {
  138.     int pos = ID_to_HeapIdx[ID];
  139.     h[pos] = h[heap_size - 1];
  140.     h.pop_back();
  141.     heap_size--;
  142.     siftdown(ID, HeapIdx_to_ID);
  143. }
  144.  
  145.  
  146. void Heap::out(void)
  147. {
  148.  
  149.     for (int i = 0; i < heap_size; i++)
  150.     {
  151.         cout << h[i] << " ";
  152.     }
  153.     cout << endl;
  154. }
  155.  
  156. int main()
  157. {
  158.    
  159.     /*
  160.         void siftup(int ID,std::vector<int>& HeapIdx_to_ID);
  161.     void siftdown(int ID,std::vector<int>& HeapIdx_to_ID);
  162.     void add(int vertex,int ID,std::vector<int>& HeapIdx_to_ID);
  163.     void delete_vertex(int ID,std::vector<int>& HeapIdx_to_ID);
  164.     bool isempty();
  165.     void out();
  166.     int* get_root();
  167.     */
  168.     int ID = -1;
  169.     std::vector<int> HeapIdx_to_ID;
  170.     Heap heap;
  171.    
  172.     //ID++;
  173.     cout << "--------" << endl;
  174.     ID++;
  175.     heap.add(1,ID,HeapIdx_to_ID);
  176.     cout << "heap: ";
  177.     heap.out();
  178.     cout << "root" << heap.get_root() << endl;
  179.     cout << HeapIdx_to_ID.size() << endl;
  180.     cout << "--------" << endl;
  181.     cout << "root" << heap.get_root() << endl;
  182.     ID++;
  183.     heap.add(3,ID,HeapIdx_to_ID);
  184.     cout << "heap: ";
  185.     heap.out();
  186.     cout << "root" << heap.get_root() << endl;
  187.     cout << HeapIdx_to_ID.size() << endl;
  188.     cout << "--------" << endl;
  189.     ID++;
  190.     heap.add(2,ID,HeapIdx_to_ID);
  191.     cout << "heap: ";
  192.     heap.out();
  193.     cout << "root" << heap.get_root() << endl;
  194.     cout << "--------" << endl;
  195.     cout << "de \n";
  196.     heap.delete_vertex(2,HeapIdx_to_ID);
  197.     heap.out();
  198.  
  199.     return 0;
  200. }
  201.  
Advertisement
Add Comment
Please, Sign In to add comment