Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- enum sort_type
- {
- heap_max = 0,
- heap_min = 1
- };
- struct heap_elements
- {
- int value;
- int own_ID;
- };
- bool operator<(const heap_elements& a, const heap_elements& b)
- {
- return (a.value < b.value);
- }
- class Heap
- {
- std::vector<struct heap_elements> h;
- int heap_size;
- public:
- Heap();
- bool isempty();
- heap_elements get_top();
- void siftup(int sort_type, std::vector<int>& ID_to_Index);
- void siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index);
- void swap(int i, int j, std::vector<int>& ID_to_Index);
- void add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index);
- void delete_vertex(int sort_type, int ID, std::vector<int>& ID_to_Index);
- void out();
- void print_vector(std::vector<int>& vector);
- };
- Heap::Heap()
- {
- std::vector<struct heap_elements> h;
- heap_size = 0;
- }
- heap_elements Heap::get_top()
- {
- return h[0];
- }
- bool Heap::isempty()
- {
- if (heap_size == 0)
- return true;
- return false;
- }
- void Heap::swap(int i, int j, std::vector<int>& ID_to_Index)
- {
- heap_elements buff;
- buff = h[i];
- h[i] = h[j];
- h[j] = buff;
- ID_to_Index[h[i].own_ID] = i; //На местах в этом массиве лежат айди этой кучи все ок
- ID_to_Index[h[j].own_ID] = j;
- }
- void Heap::siftup(int sort_type, std::vector<int>& ID_to_Index)
- {
- int curr = heap_size - 1;
- int parent = (curr - 1) / 2;
- while (curr > 0 & parent >= 0)
- {
- if (sort_type == heap_max & h[parent] < h[curr])
- swap(parent, curr, ID_to_Index);
- if (sort_type == heap_min & h[curr] < h[parent])
- swap(parent, curr, ID_to_Index);
- curr = parent;
- parent = (curr - 1) / 2;
- }
- }
- void Heap::siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index)
- {
- int parent, max_child;
- int curr = pos;
- int child_l = 2 * curr + 1;
- int child_r = 2 * curr + 2;
- //max_child = (h[child_r] < h[child_l]) ? child_l : child_r;
- if (h[child_r] < h[child_l])
- max_child = child_l;
- else
- max_child = child_r;
- while (child_l < heap_size)
- {
- if (child_l == heap_size - 1)
- max_child = child_l;
- else if (h[child_r] < h[child_l])
- max_child = child_l;
- else
- max_child = child_r;
- if (sort_type == heap_max & h[curr] < h[max_child])
- swap(curr, max_child, ID_to_Index);
- if (sort_type == heap_min & h[max_child] < h[curr])
- swap(curr, max_child, ID_to_Index);
- curr = max_child;
- child_l = 2 * curr + 1;
- child_r = 2 * curr + 2;
- }
- }
- void Heap::print_vector(std::vector<int>& vector)
- {
- if (vector.size() == 0)
- cout << "None " << endl;
- else {
- cout << "vector: ";
- for (int i = 0; i < vector.size() - 1; i++)
- cout << vector[i] << ", ";
- cout << vector[vector.size() - 1] << ";" << endl;
- }
- }
- void Heap::add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index)
- {
- heap_elements vertex;
- vertex.value = value;
- vertex.own_ID = ID;
- h.push_back(vertex);
- //Если это новое добавление, то надо делать пушбек,
- //а если старое, то надо просто на место ID написать heap_size
- cout << "Сейчас будем добавлять. Но новый или старый?" << endl;
- cout << "ID_to_Index.size() = " << ID_to_Index.size() << endl;
- cout << "heap_size = " << heap_size << endl;
- cout << "ID = " << ID << endl;
- if (ID < ID_to_Index.size()) {
- cout << "Значит это старый, ID_to_Index до" << endl;
- print_vector(ID_to_Index);
- ID_to_Index[ID] = heap_size;
- cout << "After";
- print_vector(ID_to_Index);
- }
- else {
- cout << "Значит это новый, ID_to_Index до" << endl;
- print_vector(ID_to_Index);
- ID_to_Index.push_back(heap_size); //должно быть общее у двух куч
- cout << "After";
- print_vector(ID_to_Index);
- }
- heap_size++;
- siftup(sort_type, ID_to_Index);
- }
- void Heap::delete_vertex(int sort_type, int ID, std::vector<int>& ID_to_Index)
- {
- print_vector(ID_to_Index);
- int pos = ID_to_Index[ID];
- cout << "Вызвали удаление, ID = " << ID << endl;
- cout << "pos = " << pos << endl;
- swap(pos, heap_size - 1, ID_to_Index); //Можно не делать свап
- h.pop_back();
- heap_size--;
- ID_to_Index[ID] = -1; //мб убрать
- siftdown(sort_type, pos, ID_to_Index);
- }
- void Heap::out(void)
- {
- if (heap_size == 0)
- cout << "heap: None " << endl;
- else
- {
- cout << "heap: ";
- for (int i = 0; i < heap_size - 1; i++)
- cout << h[i].value << ", ";
- cout << h[heap_size - 1].value << ";" << endl;
- }
- }
- void print_vector(std::vector<int>& vector)
- {
- cout << "vector: ";
- for (int i = 0; i < vector.size() - 1; i++)
- cout << vector[i] << ", ";
- cout << vector[vector.size() - 1] << ";" << endl;
- }
- int main()
- {
- Heap heap1;
- Heap heap2;
- std::vector<int> ID_to_Index;
- int NumberHeap;
- int curr_ID = 0;
- char c;
- int N, M, K, ID, ID_root1, root2_ID, ID_root2, count = 1;
- N = 7;
- M = 4;
- K = 2;
- int R = 0, L = 0;
- int a[N] = { 4, 2, 1, 3, 6, 5, 7 };
- //int a[N] = { 5, 6, 7, 8 };
- int ID_to_HeapNumber[N]; //При перебрасывании в другую кучу
- heap1.add(heap_max, curr_ID, a[0], ID_to_Index);
- ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
- curr_ID++;
- heap1.out();
- heap2.out();
- for (int i = 0; i < M; ++i)
- {
- cout << "----------------" << endl;
- cin >> c;
- if (c == 'R')
- {
- count++;
- R++;
- cout << "R; R = " << R << " count =" << count << endl;
- if (count < K)
- {
- cout << "count < K, просто добавляю в кучу1" << endl;
- heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
- ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
- curr_ID++;
- cout << "--------------------ANSWER--------------: "
- << "-1" << endl;
- heap1.out();
- heap2.out();
- }
- if (count == K)
- {
- cout << "count == K, просто добавляю в кучу" << endl;
- heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
- ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
- curr_ID++;
- cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
- heap1.out();
- heap2.out();
- }
- if (count > K)
- {
- cout << "count > K, Появились лишние - Надо решить куда кидать" << endl;
- if (a[R] > heap1.get_top().value)
- {
- cout << "a[R] > корня - во 2 кучу просто" << endl;
- heap2.add(heap_min, curr_ID, a[R], ID_to_Index);
- ID_to_HeapNumber[curr_ID] = 2; //Обновляю ID_to_HeapNumber
- curr_ID++;
- cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
- heap1.out(); heap2.out();
- }
- if (a[R] <= heap1.get_top().value)
- {
- cout << "a[R] <= корня - корень во 2 кучу " << endl;
- heap_elements root1, root2;
- //Запоминаю корень 1 кучи
- root1 = heap1.get_top();
- ID_root1 = root1.own_ID;
- cout << "удаляю корень 1 кучи из 1 кучи" << endl;
- // удаляю корень 1 кучи из 1 кучи
- heap1.delete_vertex(heap_max, ID_root1, ID_to_Index);
- heap1.out(); heap2.out();
- cout << "Добавляю корень 1 кучи во 2 кучу не меняя ID" << endl;
- // Добавляю корень 1 кучи во 2 кучу не меняя ID
- heap2.add(heap_min, ID_root1, root1.value, ID_to_Index);
- ID_to_HeapNumber[ID_root1] = 2; //Обновляю ID_to_HeapNumber
- heap1.out(); heap2.out();
- cout << "Добавляю в 1 кучу a[R] меняя айди" << endl;
- //Добавляю в 1 кучу a[R] меняя айди
- heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
- ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
- curr_ID++;
- heap1.out(); heap2.out();
- cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
- }
- }
- }
- else
- {
- L++;
- count--;
- cout << "L,count = " << L << " " << count << endl;
- cout << "Удаляем a[L-1]" << endl;
- ID = L - 1;
- NumberHeap = ID_to_HeapNumber[ID];
- cout << "NumberHeap = " << NumberHeap << endl;
- cout << " Если лежит в куче1 то удаляем там, иначе во 2 " << endl;
- //Если лежит в куче1 то удаляем там, иначе во 2
- if (NumberHeap == 1)
- heap1.delete_vertex(heap_max, ID, ID_to_Index);
- else
- heap2.delete_vertex(heap_min, ID, ID_to_Index);
- heap1.out();
- heap2.out();
- if (count >= K)
- {
- cout << "count >= K; В 1 куче к-1, во 2 не пусто" << endl;
- //Если удалили из 2 кучи, то первая не пострадала и просто принтим
- if (NumberHeap == 2)
- {
- cout << "удалили из 2 кучи, то первая не пострадала и просто принтим " << endl;
- cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
- }
- else
- {
- cout << "удалили из 1 кучи - надо восстановить баланс";
- //Запоминаю вершину кучи2
- heap_elements root2 = heap2.get_top();
- root2_ID = root2.own_ID;
- cout << "//Удаляем вершину кучи2, т.к. она будет в куче1" << endl;
- //Удаляем вершину кучи2, т.к. теперь она в куче1
- heap2.delete_vertex(heap_min, root2_ID, ID_to_Index);
- heap1.out(); heap2.out();
- cout << "Добавляем вершину кучи2 в кучу1 не меняя индекс чтобы стало K штук" << endl;
- //Добавляем вершину кучи2 в кучу1 не меняя индекс чтобы стало K штук
- heap1.add(heap_max, root2_ID, root2.value, ID_to_Index);
- ID_to_HeapNumber[root2_ID] = 1; //Обновляю ID_to_HeapNumber
- cout << "--------------------ANSWER--------------: " << heap1.get_top().value << endl;
- heap1.out(); heap2.out();
- }
- }
- else
- {
- cout << "--------------------ANSWER--------------: -1 " << endl;
- }
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment