vadimk772336

Работает много принтов

Nov 2nd, 2021 (edited)
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. enum sort_type
  6. {
  7.     heap_max = 0,
  8.     heap_min = 1
  9. };
  10.  
  11. struct heap_elements
  12. {
  13.     int value;
  14.     int own_ID;
  15. };
  16.  
  17. bool operator<(const heap_elements& a, const heap_elements& b)
  18. {
  19.     return (a.value < b.value);
  20. }
  21.  
  22. class Heap
  23. {
  24.     std::vector<struct heap_elements> h;
  25.     int heap_size;
  26.  
  27. public:
  28.     Heap();
  29.     bool isempty();
  30.     heap_elements get_top();
  31.     void siftup(int sort_type, std::vector<int>& ID_to_Index);
  32.     void siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index);
  33.     void swap(int i, int j, std::vector<int>& ID_to_Index);
  34.     void add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index);
  35.     void delete_vertex(int sort_type,  int ID, std::vector<int>& ID_to_Index);
  36.     void out();
  37.     void print_vector(std::vector<int>& vector);
  38. };
  39.  
  40. Heap::Heap()
  41. {
  42.     std::vector<struct heap_elements> h;
  43.     heap_size = 0;
  44. }
  45.  
  46. heap_elements Heap::get_top()
  47. {
  48.     return h[0];
  49. }
  50.  
  51. bool Heap::isempty()
  52. {
  53.     if (heap_size == 0)
  54.         return true;
  55.     return false;
  56. }
  57.  
  58. void Heap::swap(int i, int j, std::vector<int>& ID_to_Index)
  59. {
  60.     heap_elements buff;
  61.     buff = h[i];
  62.     h[i] = h[j];
  63.     h[j] = buff;
  64.  
  65.     ID_to_Index[h[i].own_ID] = i; //На местах в этом массиве лежат айди этой кучи все ок
  66.     ID_to_Index[h[j].own_ID] = j;
  67. }
  68.  
  69. void Heap::siftup(int sort_type, std::vector<int>& ID_to_Index)
  70. {
  71.     int curr = heap_size - 1;
  72.     int parent = (curr - 1) / 2;
  73.     while (curr > 0 & parent >= 0)
  74.     {
  75.         if (sort_type == heap_max & h[parent] < h[curr])
  76.             swap(parent, curr, ID_to_Index);
  77.            
  78.         if (sort_type == heap_min & h[curr] < h[parent])
  79.             swap(parent, curr, ID_to_Index);
  80.  
  81.         curr = parent;
  82.         parent = (curr - 1) / 2;
  83.     }
  84. }
  85.  
  86. void Heap::siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index)
  87. {
  88.  
  89.     int parent, max_child;
  90.  
  91.     int curr = pos;
  92.     int child_l = 2 * curr + 1;
  93.     int child_r = 2 * curr + 2;
  94.  
  95.     //max_child = (h[child_r] < h[child_l]) ? child_l : child_r;
  96.  
  97.     if (h[child_r] < h[child_l])
  98.         max_child = child_l;
  99.     else
  100.         max_child = child_r;
  101.  
  102.     while (child_l < heap_size)
  103.     {
  104.         if (child_l == heap_size - 1)
  105.             max_child = child_l;
  106.         else if (h[child_r] < h[child_l])
  107.             max_child = child_l;
  108.         else
  109.             max_child = child_r;
  110.  
  111.        
  112.         if (sort_type == heap_max & h[curr] < h[max_child])
  113.             swap(curr, max_child, ID_to_Index);
  114.            
  115.         if (sort_type == heap_min & h[max_child] < h[curr])
  116.             swap(curr, max_child, ID_to_Index);
  117.  
  118.         curr = max_child;
  119.         child_l = 2 * curr + 1;
  120.         child_r = 2 * curr + 2;
  121.     }
  122. }
  123.  
  124. void Heap::print_vector(std::vector<int>& vector)
  125. {
  126.     if (vector.size() == 0)
  127.         cout << "None " << endl;
  128.     else {
  129.         cout << "vector: ";
  130.         for (int i = 0; i < vector.size() - 1; i++)
  131.             cout << vector[i] << ", ";
  132.         cout << vector[vector.size() - 1] << ";" << endl;
  133.     }
  134. }
  135.  
  136. void Heap::add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index)
  137. {
  138.     heap_elements vertex;
  139.     vertex.value = value;
  140.     vertex.own_ID = ID;
  141.  
  142.     h.push_back(vertex);
  143.    
  144.  
  145.     //Если это новое добавление, то надо делать пушбек,
  146.     //а если старое, то надо просто на место ID написать heap_size
  147.     cout << "Сейчас будем добавлять. Но новый или старый?" << endl;
  148.     cout << "ID_to_Index.size() = "  << ID_to_Index.size() << endl;
  149.     cout << "heap_size = "  << heap_size << endl;
  150.     cout << "ID = "  << ID << endl;
  151.    
  152.     if (ID < ID_to_Index.size()) {
  153.         cout << "Значит это старый, ID_to_Index до" << endl;
  154.         print_vector(ID_to_Index);
  155.         ID_to_Index[ID] = heap_size;
  156.         cout << "After";
  157.         print_vector(ID_to_Index);
  158.     }
  159.     else {
  160.         cout << "Значит это новый, ID_to_Index до" << endl;
  161.         print_vector(ID_to_Index);
  162.         ID_to_Index.push_back(heap_size); //должно быть общее у двух куч
  163.         cout << "After";
  164.         print_vector(ID_to_Index);
  165.     }
  166.     heap_size++;
  167.     siftup(sort_type, ID_to_Index);
  168. }
  169.  
  170. void Heap::delete_vertex(int sort_type, int ID, std::vector<int>& ID_to_Index)
  171. {
  172.  
  173.     print_vector(ID_to_Index);
  174.     int pos = ID_to_Index[ID];
  175.    
  176.     cout << "Вызвали удаление, ID = " << ID << endl;
  177.     cout << "pos = " << pos << endl;
  178.  
  179.     swap(pos, heap_size - 1, ID_to_Index); //Можно не делать свап
  180.     h.pop_back();
  181.     heap_size--;
  182.     ID_to_Index[ID] = -1; //мб убрать
  183.     siftdown(sort_type, pos, ID_to_Index);
  184. }
  185.  
  186. void Heap::out(void)
  187. {
  188.     if (heap_size == 0)
  189.         cout << "heap: None " << endl;
  190.     else
  191.     {
  192.         cout << "heap: ";
  193.         for (int i = 0; i < heap_size - 1; i++)
  194.             cout << h[i].value << ", ";
  195.    
  196.         cout << h[heap_size - 1].value << ";" << endl;
  197.     }
  198. }
  199.  
  200. void print_vector(std::vector<int>& vector)
  201. {
  202.     cout << "vector: ";
  203.     for (int i = 0; i < vector.size() - 1; i++)
  204.         cout << vector[i] << ", ";
  205.     cout << vector[vector.size() - 1] << ";" << endl;
  206. }
  207.  
  208.  
  209. int main()
  210. {
  211.  
  212.     Heap heap1;
  213.     Heap heap2;
  214.    
  215.     std::vector<int> ID_to_Index;
  216.     int NumberHeap;
  217.     int curr_ID = 0;
  218.     char c;
  219.  
  220.     int N, M, K, ID, ID_root1, root2_ID, ID_root2, count = 1;
  221.     N = 7;
  222.     M = 4;
  223.     K = 2;
  224.     int R = 0, L = 0;
  225.     int a[N] = { 4, 2, 1, 3, 6, 5, 7 };
  226.     //int a[N] = { 5, 6, 7, 8 };
  227.     int ID_to_HeapNumber[N]; //При перебрасывании в другую кучу
  228.    
  229.     heap1.add(heap_max, curr_ID, a[0], ID_to_Index);
  230.     ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  231.     curr_ID++;
  232.     heap1.out();
  233.     heap2.out();
  234.  
  235.     for (int i = 0; i < M; ++i)
  236.     {
  237.         cout << "----------------" << endl;
  238.         cin >> c;
  239.  
  240.         if (c == 'R')
  241.         {
  242.             count++;
  243.             R++;
  244.            
  245.             cout << "R; R = " << R << " count =" << count << endl;
  246.  
  247.             if (count < K)
  248.             {
  249.                 cout << "count < K, просто добавляю в кучу1" << endl;
  250.  
  251.                 heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
  252.                 ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  253.                 curr_ID++;
  254.  
  255.                 cout << "--------------------ANSWER--------------: "
  256.                      << "-1" << endl;
  257.  
  258.                 heap1.out();
  259.                 heap2.out();
  260.             }
  261.  
  262.             if (count == K)
  263.             {
  264.                 cout << "count == K, просто добавляю в кучу" << endl;
  265.  
  266.                 heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
  267.                 ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  268.                 curr_ID++;
  269.  
  270.                 cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
  271.  
  272.                 heap1.out();
  273.                 heap2.out();
  274.             }
  275.  
  276.             if (count > K)
  277.             {
  278.                 cout << "count > K, Появились лишние - Надо решить куда кидать" << endl;
  279.  
  280.                 if (a[R] > heap1.get_top().value)
  281.                 {
  282.                     cout << "a[R] > корня - во 2 кучу просто" << endl;
  283.  
  284.                     heap2.add(heap_min, curr_ID, a[R], ID_to_Index);
  285.                     ID_to_HeapNumber[curr_ID] = 2; //Обновляю ID_to_HeapNumber
  286.                     curr_ID++;
  287.  
  288.                     cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
  289.  
  290.                     heap1.out(); heap2.out();
  291.                    
  292.                 }
  293.  
  294.                 if (a[R] <= heap1.get_top().value)
  295.  
  296.                 {
  297.                     cout << "a[R] <= корня - корень во 2 кучу  " << endl;
  298.  
  299.                     heap_elements root1, root2;
  300.  
  301.                     //Запоминаю корень 1 кучи
  302.                     root1 = heap1.get_top();
  303.                     ID_root1 = root1.own_ID;
  304.                    
  305.                     cout << "удаляю корень 1 кучи из 1 кучи" << endl;
  306.                     // удаляю корень 1 кучи из 1 кучи
  307.                     heap1.delete_vertex(heap_max, ID_root1, ID_to_Index);
  308.                     heap1.out(); heap2.out();
  309.                    
  310.                     cout << "Добавляю корень 1 кучи во 2 кучу не меняя ID" << endl;
  311.                     // Добавляю корень 1 кучи во 2 кучу не меняя ID
  312.                     heap2.add(heap_min, ID_root1, root1.value, ID_to_Index);
  313.                     ID_to_HeapNumber[ID_root1] = 2; //Обновляю ID_to_HeapNumber
  314.                     heap1.out(); heap2.out();
  315.                    
  316.                    
  317.                     cout << "Добавляю в 1 кучу a[R]  меняя айди" << endl;
  318.                     //Добавляю в 1 кучу a[R]  меняя айди
  319.                     heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
  320.                     ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
  321.                     curr_ID++;
  322.                     heap1.out(); heap2.out();
  323.                    
  324.                     cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
  325.  
  326.                    
  327.                 }
  328.             }
  329.         }
  330.         else
  331.         {
  332.             L++;
  333.             count--;
  334.  
  335.             cout << "L,count = " << L << " " << count << endl;
  336.  
  337.             cout << "Удаляем a[L-1]" << endl;
  338.  
  339.             ID = L - 1;
  340.             NumberHeap = ID_to_HeapNumber[ID];
  341.            
  342.             cout << "NumberHeap = " << NumberHeap << endl;
  343.  
  344.             cout << " Если лежит в куче1 то удаляем там, иначе во 2 " << endl;
  345.             //Если лежит в куче1 то удаляем там, иначе во 2
  346.             if (NumberHeap == 1)
  347.                 heap1.delete_vertex(heap_max, ID, ID_to_Index);
  348.             else
  349.                 heap2.delete_vertex(heap_min, ID, ID_to_Index);
  350.  
  351.             heap1.out();
  352.             heap2.out();
  353.  
  354.             if (count >= K)
  355.             {
  356.                 cout << "count >= K; В 1 куче к-1, во 2 не пусто" << endl;
  357.                
  358.                
  359.                 //Если удалили из 2 кучи, то первая не пострадала и просто принтим
  360.                 if (NumberHeap == 2)
  361.                 {
  362.                     cout << "удалили из 2 кучи, то первая не пострадала и просто принтим " << endl;
  363.                     cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
  364.                 }
  365.                
  366.                 else
  367.                 {
  368.                     cout << "удалили из 1 кучи - надо восстановить баланс";
  369.                     //Запоминаю вершину кучи2
  370.                     heap_elements root2 = heap2.get_top();
  371.                     root2_ID = root2.own_ID;
  372.                    
  373.                     cout << "//Удаляем вершину кучи2, т.к. она будет в куче1" << endl;
  374.                     //Удаляем вершину кучи2, т.к. теперь она в куче1
  375.                     heap2.delete_vertex(heap_min, root2_ID, ID_to_Index);
  376.                     heap1.out(); heap2.out();
  377.                    
  378.                     cout << "Добавляем вершину кучи2 в кучу1  не меняя индекс чтобы стало K штук" << endl;
  379.                     //Добавляем вершину кучи2 в кучу1  не меняя индекс чтобы стало K штук
  380.                     heap1.add(heap_max, root2_ID, root2.value, ID_to_Index);
  381.                     ID_to_HeapNumber[root2_ID] = 1; //Обновляю ID_to_HeapNumber
  382.                    
  383.                     cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
  384.                     heap1.out(); heap2.out();
  385.                 }
  386.  
  387.             }
  388.             else
  389.             {
  390.                 cout << "--------------------ANSWER--------------: -1 " << endl;
  391.             }
  392.         }
  393.     }
  394.  
  395.     return 0;
  396. }
  397.  
  398.  
Add Comment
Please, Sign In to add comment