Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // Created by larik on 11.10.2019.
- //
- #include <iostream>
- #include <vector>
- #include <utility>
- #include <algorithm>
- class BinHeap {
- private:
- std::vector<std::pair<int, std::pair<int, int>>> elems;
- int parent(int ii) {
- return (ii - 1) / 2;
- }
- int left(int ii) {
- return (2 * ii + 1);
- }
- int right(int ii) {
- return (2 * ii + 2);
- }
- void heap_up(int ii) {
- if (ii && elems[parent(ii)].first > elems[ii].first) {
- std::swap(elems[ii], elems[parent(ii)]);
- heap_up(parent(ii));
- }
- }
- void heap_down(int ii) {
- int ll = left(ii), rr = right(ii), cur = ii;
- if (ll < size() && elems[ll].first < elems[cur].first) {
- cur = ll;
- }
- if (rr < size() && elems[rr].first < elems[cur].first) {
- cur = rr;
- }
- if (cur != ii) {
- std::swap(elems[ii], elems[cur]);
- heap_down(cur);
- }
- }
- public:
- int size() {
- return elems.size();
- }
- std::pair<int, std::pair<int, int>> root() {
- return elems[0];
- }
- void pop() {
- elems[0] = elems.back();
- elems.pop_back();
- heap_down(0);
- }
- void push(std::pair<int, std::pair<int, int>> elem) {
- elems.push_back(elem);
- heap_up(size() - 1);
- }
- };
- int main() {
- int nn, mm;
- std::cin >> nn >> mm;
- BinHeap heap;
- std::vector<std::vector<int>> data(nn);
- for (int i = 0; i < nn; ++i) {
- data[i].resize(mm);
- for (int j = 0; j < mm; ++j) {
- int elem;
- std::cin >> elem;
- data[i][j] = elem;
- }
- }
- std::vector<int> result;
- for (int i = 0; i < nn; ++i) {
- heap.push(std::pair(data[i][0], std::pair(i, 0)));
- }
- while (heap.size() > 0) {
- std::pair<int, std::pair<int, int>> min;
- min = heap.root();
- heap.pop();
- std::cout << min.first << ' ';
- int ii = min.second.first, jj = min.second.second;
- if (jj < mm - 1) {
- heap.push(std::pair(data[ii][jj + 1], std::pair(ii, jj + 1)));
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement