Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <ios>
- #include <iostream>
- #include <climits>
- #include <assert.h>
- #include <cstring>
- class Heap {
- private:
- // array
- long long *buffer;
- int *node_buffer;
- int *point_buffer;
- // size of arrays
- int buffer_size;
- int query_size;
- int size;
- int query_iter;
- public:
- Heap() {
- buffer_size = 100;
- query_size = 100;
- size = 0;
- query_iter = 0;
- buffer = new long long[buffer_size];
- node_buffer = new int[query_size];
- point_buffer = new int[query_size];
- }
- ~Heap() {
- delete[] buffer;
- delete[] node_buffer;
- delete[] point_buffer;
- }
- int Parent(int ind) { return ind / 2; }
- void GrowBuffer() {
- buffer_size *= 2;
- long long* new_buffer = new long long[buffer_size];
- memcpy(new_buffer, buffer, (size + 1) * sizeof(long long));
- delete[] buffer;
- buffer = new_buffer;
- }
- void GrowQuery() {
- query_size *= 2;
- int* new_node_buffer = new int[query_size];
- int* new_point_buffer = new int[query_size];
- memcpy(new_node_buffer, node_buffer, (query_iter + 1) * sizeof(int));
- memcpy(new_point_buffer, point_buffer, (query_iter + 1) * sizeof(int));
- delete[] node_buffer;
- delete[] point_buffer;
- node_buffer = new_node_buffer;
- point_buffer = new_point_buffer;
- }
- void ChangeTwoPoints(int f_node, int s_node) {
- int query_of_first = node_buffer[f_node],
- query_of_second = node_buffer[s_node];
- point_buffer[query_of_first] = s_node;
- point_buffer[query_of_second] = f_node;
- node_buffer[f_node] = query_of_second;
- node_buffer[s_node] = query_of_first;
- std::swap(buffer[f_node], buffer[s_node]);
- }
- void SiftUp(int v) {
- while (v > 1) {
- if (buffer[v] < buffer[Parent(v)]) {
- ChangeTwoPoints(v, Parent(v));
- v /= 2;
- } else {
- break;
- }
- }
- }
- void SiftDown(int v) {
- while (2 * v <= size) {
- int u = 2 * v;
- if (((u + 1) <= size) && (buffer[u + 1] < buffer[u])) {
- u = 2 * v + 1;
- }
- if (buffer[u] < buffer[v]) {
- ChangeTwoPoints(u, v);
- v = u;
- } else {
- break;
- }
- }
- }
- void Insert(long long x) {
- if (size >= buffer_size - 1) {
- GrowBuffer();
- }
- if (query_iter >= query_size - 1) {
- GrowQuery();
- }
- ++size;
- ++query_iter;
- buffer[size] = x;
- point_buffer[query_iter] = size;
- node_buffer[size] = query_iter;
- SiftUp(size);
- }
- long long GetMin() {
- if (query_iter >= query_size - 1) {
- GrowQuery();
- }
- ++query_iter;
- return buffer[1];
- }
- void DecreaseKey(int query, long long diff) {
- if (query_iter >= query_size - 1) {
- GrowQuery();
- }
- ++query_iter;
- int ind = point_buffer[query];
- buffer[ind] -= diff;
- SiftUp(ind);
- }
- void ExtractMin() {
- if (query_iter >= query_size - 1) {
- GrowQuery();
- }
- ++query_iter;
- ChangeTwoPoints(1, size);
- buffer[size--] = 1e9 + 7;
- SiftDown(1);
- }
- };
- int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr); std::cout.tie(nullptr);
- Heap heap;
- int q;
- std::cin >> q;
- while (q--) {
- std::string inputCommand;
- std::cin >> inputCommand;
- if (inputCommand == "insert") {
- long long insert_numb;
- std::cin >> insert_numb;
- heap.Insert(insert_numb);
- } else if (inputCommand == "getMin") {
- std::cout << heap.GetMin() << "\n";
- } else if (inputCommand == "extractMin") {
- heap.ExtractMin();
- } else if (inputCommand == "decreaseKey"){
- int query;
- long long diff;
- std::cin >> query >> diff;
- heap.DecreaseKey(query, diff);
- } else {
- return 0;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement