Advertisement
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 dots
- {
- int l;
- int r;
- int to_heap;
- int number_heap = 0;
- };
- struct heap_element
- {
- int l;
- int r;
- int pos;
- dots* to_list;
- };
- bool operator<(const heap_element& a, const heap_element& b)
- {
- if ((a.l < b.l))
- return true;
- return false;
- }
- class Heap
- {
- std::vector<struct heap_element> h;
- int heap_size;
- public:
- Heap();
- void siftup(int sort_type, int pos);
- void siftdown(int sort_type, int pos);
- void my_swap(int i, int j);
- void add(int sort_type, int l, int r, dots* to_list);
- void del(int sort_type, int pos);
- bool isempty();
- heap_element* get_top();
- int size();
- void out();
- };
- Heap::Heap()
- {
- std::vector<struct heap_element> h;
- heap_size = 0;
- }
- void Heap::out(void)
- {
- for (int i = 0; i < heap_size; i++)
- {
- cout << "(" << h[i].l << "," << h[i].r << ") ";
- }
- cout << endl;
- }
- int Heap::size()
- {
- return this->heap_size;
- }
- heap_element* Heap::get_top()
- {
- return &h[0];
- }
- bool Heap::isempty()
- {
- if (heap_size == 0)
- return true;
- return false;
- }
- void Heap::my_swap(int i, int j)
- {
- heap_element buffer;
- buffer = h[i];
- h[i] = h[j];
- h[j] = buffer;
- h[i].pos = i;
- h[j].pos = j;
- h[i].to_list->to_heap = i;
- h[j].to_list->to_heap = j;
- }
- void Heap::siftup(int sort_type, int pos)
- {
- int curr = pos;
- int parent = (curr - 1) / 2;
- while (parent >= 0 & curr > 0)
- {
- if (sort_type == heap_max & h[parent] < h[curr])
- my_swap(parent, curr);
- if (sort_type == heap_min & h[curr] < h[parent])
- my_swap(parent, curr);
- curr = parent;
- parent = (curr - 1) / 2;
- }
- }
- void Heap::siftdown(int sort_type, int pos)
- {
- int parent, max_child, min_child;
- int curr = pos;
- int child_l = 2 * curr + 1;
- int child_r = 2 * curr + 2;
- while (child_l < heap_size)
- {
- if (sort_type == heap_max)
- {
- max_child = child_l;
- if (child_r < heap_size & h[child_l] < h[child_r])
- max_child = child_r;
- if (h[curr] < h[max_child])
- my_swap(curr, max_child);
- curr = max_child;
- child_l = 2 * curr + 1;
- child_r = 2 * curr + 2;
- }
- if (sort_type == heap_min)
- {
- if (child_l == heap_size - 1)
- min_child = child_l;
- else if (h[child_r] < h[child_l])
- min_child = child_r;
- else
- min_child = child_l;
- if (h[min_child] < h[curr])
- {
- my_swap(curr, min_child);
- }
- curr = min_child;
- child_l = 2 * curr + 1;
- child_r = 2 * curr + 2;
- }
- }
- }
- void Heap::add(int sort_type, int l, int r, dots* to_list)
- {
- this->heap_size++;
- heap_element vertex;
- vertex.l = l;
- vertex.r = r;
- vertex.to_list = to_list;
- vertex.pos = heap_size - 1;
- h.push_back(vertex);
- to_list->to_heap = heap_size - 1;
- siftup(sort_type, heap_size - 1);
- }
- void Heap::del(int sort_type, int pos)
- {
- h[pos] = h[heap_size - 1];
- h[pos].pos = pos;
- h[pos].to_list->to_heap = pos;
- h.pop_back();
- this->heap_size--;
- int parent = (pos - 1) / 2;
- if (sort_type == heap_max)
- {
- if (h[parent] < h[pos])
- siftup(sort_type, pos);
- else
- siftdown(sort_type, pos);
- }
- if (sort_type == heap_min)
- {
- if (h[pos] < h[parent])
- siftup(sort_type, pos);
- else
- siftdown(sort_type, pos);
- }
- }
- int main()
- {
- Heap heap1;
- Heap heap2;
- int count_requests;
- cin >> count_requests;
- dots requests[count_requests];
- dots dot;
- char c,x,y;
- int a,b;
- cin >> c;
- while (c == "Q")
- {
- cout << -1 << endl;
- cin >> c;
- }
- cin >> x >> y;
- a = stoi(x);
- b = stoi(y);
- dot.l = a;
- dot.r = b;
- dot.number_heap = 2;
- requests[0] = dot;
- heap2.add(heap_min, a,b,&requests[0]);
- for (int = 0; i < count_requests; ++i)
- {
- cin >> c;
- if (c == "Q")
- heap.display_current_line();
- else
- {
- cin >> x >> y;
- int x = std::stoi(x);
- int y = std::stoi(y);
- if (c == "D")
- {
- flag = true;
- j = 0;
- while (flag)
- {
- if requests[j].l == x & requests[j].r == y
- }
- }
- else
- {
- }
- }
- }
- //a.l = 2;
- //a.r = 2;
- //requests[0] = a;
- //heap.add(heap_max,2,2,&requests[0]);
- //heap.out();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement