KShah

Untitled

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