KShah

Untitled

Oct 23rd, 2021
644
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <ios>
  2. #include <iostream>
  3. #include <climits>
  4. #include <assert.h>
  5. #include <cstring>
  6.  
  7. class Heap {
  8. private:
  9.     // array
  10.     long long *buffer;
  11.     int *node_buffer;
  12.     int *point_buffer;
  13.  
  14.     // size of arrays
  15.     int buffer_size;
  16.     int query_size;
  17.     int size;
  18.     int query_iter;
  19. public:
  20.     Heap() {
  21.         buffer_size = 4;
  22.         query_size = 4;
  23.        
  24.         size = 0;
  25.         query_iter = 0;
  26.  
  27.         buffer = new long long[buffer_size];
  28.         node_buffer = new int[query_size];
  29.         point_buffer = new int[query_size];
  30.  
  31.     }
  32.     ~Heap() {
  33.         delete[] buffer;
  34.         delete[] node_buffer;
  35.         delete[] point_buffer;
  36.     }
  37.        
  38.     int Parent(int ind) { return ind / 2; }
  39.    
  40.    
  41.     void GrowBuffer() {
  42.         buffer_size *= 2;
  43.         long long* new_buffer = new long long[buffer_size];
  44.         memcpy(new_buffer, buffer, (size + 1) * sizeof(long long));
  45.         delete[] buffer;
  46.         buffer = new_buffer;
  47.     }
  48.  
  49.     void GrowQuery() {
  50.         query_size *= 2;
  51.  
  52.         int* new_node_buffer = new int[query_size];
  53.         int* new_point_buffer = new int[query_size];
  54.  
  55.         memcpy(new_node_buffer, node_buffer, (query_iter + 1) * sizeof(int));
  56.         memcpy(new_point_buffer, point_buffer, (query_iter + 1) * sizeof(int));
  57.  
  58.         delete[] node_buffer;
  59.         delete[] point_buffer;
  60.  
  61.         node_buffer = new_node_buffer;
  62.         point_buffer = new_point_buffer;
  63.     }
  64.    
  65.     void ChangeTwoPoints(int f_node, int s_node) {
  66.         int query_of_first = node_buffer[f_node],
  67.             query_of_second = node_buffer[s_node];
  68.  
  69.         point_buffer[query_of_first] = s_node;
  70.         point_buffer[query_of_second] = f_node;
  71.         node_buffer[f_node] = query_of_second;
  72.         node_buffer[s_node] = query_of_first;
  73.  
  74.         std::swap(buffer[f_node], buffer[s_node]);
  75.     }
  76.    
  77.     void SiftUp(int v) {
  78.         while (v != 1) {
  79.             if (buffer[v] < buffer[Parent(v)]) {
  80.                 ChangeTwoPoints(v, Parent(v));
  81.                 v /= 2;
  82.             } else {
  83.                 break;
  84.             }
  85.         }
  86.     }
  87.  
  88.     void SiftDown(int v) {
  89.         while (2 * v <= size) {
  90.             int u = 2 * v;
  91.             if (((u + 1) <= size) && (buffer[u + 1] < buffer[u])) {
  92.                 int u = 2 * v + 1;
  93.             }      
  94.  
  95.             if (buffer[u] < buffer[v]) {
  96.                 ChangeTwoPoints(u, v);
  97.                 v = u;
  98.             } else {
  99.                 break;
  100.             }
  101.         }        
  102.     }
  103.  
  104.     void Insert(long long x) {
  105.         if (size >= buffer_size - 1) {
  106.             GrowBuffer();
  107.         }
  108.    
  109.         if (query_iter >= query_size - 1) {
  110.             GrowQuery();
  111.         }
  112.        
  113.         ++size;
  114.         ++query_iter;
  115.  
  116.         buffer[size] = x;
  117.         point_buffer[query_iter] = size;
  118.         node_buffer[size] = query_iter;
  119.          
  120.         SiftUp(size);
  121.     }
  122.  
  123.     long long GetMin() {
  124.         if (query_iter >= query_size - 1) {
  125.             GrowQuery();
  126.         }
  127.      
  128.         ++query_iter;
  129.  
  130.         return buffer[1];
  131.     }
  132.  
  133.     void ExtractMin() {
  134.         if (query_iter >= query_size - 1) {
  135.             GrowQuery();
  136.         }
  137.         ++query_iter;
  138.  
  139.         ChangeTwoPoints(1, size);
  140.         --size;
  141.         SiftDown(1);
  142.     }
  143.  
  144.     void SmartDecreaseKey(int query, long long diff) {
  145.         if (query_iter >= query_size - 1) {
  146.             GrowQuery();
  147.         }
  148.         ++query_iter;      
  149.        
  150.         int ind = point_buffer[query];
  151.         buffer[ind] -= diff;
  152.         SiftUp(ind);
  153.     }
  154.  
  155.  
  156. };
  157.    
  158. int main() {
  159.     std::ios_base::sync_with_stdio(false);
  160.     std::cin.tie(nullptr); std::cout.tie(nullptr);
  161.     Heap heap;
  162.    
  163.     int q;
  164.     std::cin >> q;
  165.  
  166.     while (q--) {
  167.         std::string inputCommand;
  168.         std::cin >> inputCommand;
  169.  
  170.         if (inputCommand == "insert") {
  171.             long long insert_numb;
  172.             std::cin >> insert_numb;
  173.             heap.Insert(insert_numb);
  174.         } else if (inputCommand == "getMin") {
  175.             std::cout << heap.GetMin() << "\n";
  176.         } else if (inputCommand == "extractMin") {
  177.             heap.ExtractMin();
  178.         } else if (inputCommand == "decreaseKey"){
  179.             int query;
  180.             long long diff;
  181.             std::cin >> query >> diff;
  182.             heap.SmartDecreaseKey(query, diff);
  183.         } else {
  184.             return 0;
  185.         }
  186.     }
  187.  
  188.     return 0;
  189. }
  190.  
  191.  
  192.  
RAW Paste Data