Seminar9

#include <iostream>
#include <queue>
#include <set>
#include <unordered_map>
#include <vector>

struct PriorityQueue {
 public:
  void Push(int v, int distance);
  // Возвращает индекс вершины
  int Pop();
  void DecreaseKey(int v, int old_distance, int distance);

  void Print() const { for (auto [d, v] : distances_and_vertices) std::cout << d << " " << v << ", "; std::cout << std::endl; }

 private:
  std::set<std::pair<int, int>> distances_and_vertices;
};

void PriorityQueue::Push(int v, int distance) {
  distances_and_vertices.insert({distance, v});
}
int PriorityQueue::Pop() {
  auto it = distances_and_vertices.begin();
  int result = it->second;
  distances_and_vertices.erase(it);
  return result;
}
void PriorityQueue::DecreaseKey(int v, int old_distance, int distance) {
  distances_and_vertices.erase({old_distance, v});
  distances_and_vertices.insert({distance, v});
}

int main1() {
  PriorityQueue pq;
  pq.Push(4, 9);
  pq.Push(1, 8);
  pq.Print();
  pq.DecreaseKey(4, 9, 7);
  pq.Print();
  return 0;
}

struct PriorityQueue2 {
 public:
  void Push(int v, int distance);
  // Возвращает индекс вершины
  int Pop();
  void DecreaseKey(int v, int distance);

  void Print() const { for (auto [d, v] : heap) std::cout << d << " " << v << ", "; std::cout << std::endl; }

 private:
  std::vector<std::pair<int, int>> heap;
  //std::vector<size_t> v2head_index;  Нужно знать, сколько вершин в такой версии
  std::unordered_map<int, size_t> v2index;

  void SiftUp(size_t pos);
  void SiftDown(size_t pos);
};

void PriorityQueue2::Push(int v, int distance) {
  heap.push_back({distance, v});
  v2index[v] = heap.size() - 1;
  SiftUp(heap.size() - 1);
}

int PriorityQueue2::Pop() {
  assert(!heap.empty());
  int result = heap.front().second;
  v2index.erase(result);
  heap[0] = heap.back();
  heap.pop_back();
  if (heap.empty()) return result;
  v2index[heap[0].second] = 0;

  SiftDown(0);
  return result;
}

void PriorityQueue2::DecreaseKey(int v, int distance) {
  size_t index = v2index[v];
  heap[index].first = distance;
  SiftUp(index);
}

void PriorityQueue2::SiftUp(size_t pos) {
  while (pos > 0) {
    size_t parent = (pos - 1) / 2;
    if (heap[parent] <= heap[pos]) break;
    v2index[heap[pos].second] = parent;
    v2index[heap[parent].second] = pos;
    std::swap(heap[parent], heap[pos]);
    pos = parent;
  }
}

void PriorityQueue2::SiftDown(size_t pos) {
  while (true) {
    size_t minimum = pos;
    size_t left = pos * 2 + 1;
    if (left < heap.size() && heap[left] < heap[minimum]) minimum = left;
    size_t right = pos * 2 + 2;
    if (right < heap.size() && heap[right] < heap[minimum]) minimum = right;
    if (minimum == pos) return;
    v2index[heap[pos].second] = minimum;
    v2index[heap[minimum].second] = pos;
    std::swap(heap[pos], heap[minimum]);
  }
}

int main3() {
  PriorityQueue2 pq;
  pq.Push(4, 9);
  pq.Push(1, 8);
  pq.Print();
  pq.DecreaseKey(4, 7);
  pq.Print();
  pq.Pop();
  pq.Print();
  return 0;
}

//class MyPair {
// public:
//  MyPair& operator=(MyPair&& from) {
//    long long shift = this - &from;
//    q.v2index[from] += shift;
//  }
//};
//int main2() {
//  //
//  priority_queue<MyPair>
//  return 0;
//}

class DSU {
 public:
  explicit DSU(int n);
  int Find(int v);
  void Union(int u, int v);
  void Print() const;

 private:
  std::vector<int> parents;
};

DSU::DSU(int n) : parents(n) {
  for (int i = 0; i < n; ++i) parents[i] = i;
}
int DSU::Find(int v) {
  while (v != parents[v]) v = parents[v];
  return v;
}
void DSU::Union(int u, int v) {
  u = Find(u);
  v = Find(v);
  parents[v] = u;
}
void DSU::Print() const {
  for (int i = 0; i < parents.size(); ++i) {
    int u = i;
    for (; u != parents[u]; u = parents[u]) std::cout << u << " -> ";
    std::cout << u << "\n";
  }
}

int main() {
  DSU dsu(10);
  dsu.Union(8, 0);
  dsu.Union(5, 0);
  dsu.Union(8, 2);
  dsu.Union(7, 5);
  dsu.Union(3, 6);
  dsu.Union(3, 9);
  dsu.Union(3, 4);
  dsu.Print();

  return 0;
}