Seminar4

#include <iostream>
#include <queue>
#include <vector>

int main0() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);

  int value = 0;
  char num = getchar();
  bool negative = num == '-';

  if ('0' <= num && num <= '9')
    value = num - '0';
  while (true) {
    num = getchar();
    if ('0' <= num && num <= '9') {
      value = value * 10 + (num - '0');
    } else {
      break;
    }
  }
  if (negative) value = -value;
  std::cout << value << std::endl;
  return 0;
}

int main1() {
  std::priority_queue<int, std::vector<int>, std::greater<>> q;
  q.push(0);  // O(log n)
  q.push(2);
  q.push(5);
  q.push(1);
  std::cout << q.top() << std::endl;  // O(1)
  q.pop();  // O(log n)
  std::cout << q.top() << std::endl;
  return 0;
}

void print(const std::vector<int>& v) {
  for (int x : v) std::cout << x << " ";
  std::cout << std::endl;
}

int main2() {
  std::vector<int> v = {6, 5, 7, 3, 2, 1, 4, 8, 9, 0};
  print(v);

  std::make_heap(v.begin() + 1, v.end() - 3);
  print(v);

  *(v.end() - 4) = 10;
  std::push_heap(v.begin() + 1, v.end() - 3);
  print(v);

  std::pop_heap(v.begin() + 1, v.end() - 3);
  print(v);

  return 0;
}

class PriorityQueue {
 public:
  void Push(int value);
  int Pop();
  bool Empty() const { return v.empty(); }

 private:
  std::vector<int> v;

  void SiftUp(size_t index);
  void SiftDown(size_t index);

};

void PriorityQueue::Push(int value) {
  v.push_back(value);
  SiftUp(v.size() - 1);
}

int PriorityQueue::Pop() {
  if (v.empty())
    throw std::runtime_error("Pop() called for empty PriorityQueue");
  int result = v.front();
  v.front() = v.back();
  v.pop_back();
  if (!Empty()) SiftDown(0);
  return result;
}

void PriorityQueue::SiftUp(size_t index) {
  while (index > 0) {
    size_t parent = (index - 1) / 2;
    if (v[parent] >= v[index]) return;
    std::swap(v[parent], v[index]);
    index = parent;
  }
}

void PriorityQueue::SiftDown(size_t index) {
//  while (true) {
//  while (1) {
//  for (;;) {
  while (true) {
    size_t left = 2 * index + 1;
    size_t right = 2 * index + 2;
    // Ищем большего сына, если такой есть.
    size_t largest = index;
    if (left < v.size() && v[left] > v[index])
      largest = left;
    if (right < v.size() && v[right] > v[largest])
      largest = right;
    // Если больший сын есть, то проталкиваем корень в него.
    if (index == largest) break;
    std::swap(v[index], v[largest]);
    index = largest;
  }
}

int main() {
  try {
    PriorityQueue q;
    q.Push(40);
    q.Push(32);
    q.Push(12);
    q.Push(57);
    q.Push(56);
    std::cout << q.Pop() << std::endl;
    std::cout << q.Pop() << std::endl;
    std::cout << q.Pop() << std::endl;
    std::cout << q.Pop() << std::endl;
    std::cout << q.Pop() << std::endl;
    std::cout << q.Pop() << std::endl;
  } catch(std::exception& e) {
    std::cout << e.what();
  }
  return 89;
}