#include <iostream>

using namespace std;

template <class T, class K>
class Heap {
public:
  Heap(int size);
  ~Heap();
  bool empty();
  bool insert(T elt, K key);
  T min();
  void removeMin();

private:
  pair<T,K> *data;
  int capacity;
  int num;
};

template <class T, class K>
Heap<T,K>::Heap(int size) {
  capacity = size;
  data = new pair<T,K>[capacity];
  num = 0;
}

template <class T, class K>
Heap<T,K>::~Heap() {
  delete [] data;
}

template <class T, class K>
bool Heap<T,K>::empty() {
  return (num == 0);
}

template <class T, class K>
bool Heap<T,K>::insert(T elt, K key) {
  if (num == capacity)
    return false;
  int v = num++;
  data[v].first = elt;
  data[v].second = key;
  while (v != 0) {
    int u = (v+1)/2-1;
    if (data[v].second > data[u].second)
      break;
    pair<T,K> tmp = data[u];
    data[u] = data[v];
    data[v] = tmp;
    v = u;
  }
  return true;
}

template <class T, class K>
T Heap<T,K>::min() {
  return data[0].first;
}

template <class T, class K>
void Heap<T,K>::removeMin() {
  data[0] = data[--num];
  int v = 0;
  while (2*v+1 < num) {
    int u = 2*v+1;
    if ((u+1 < num) && (data[u+1].second < data[u].second))
      u = u+1;
    if (data[u].second > data[v].second)
      break;
    pair<T,K> tmp = data[u];
    data[u] = data[v];
    data[v] = tmp;
    v = u;
  }
}

int main() {
  Heap<int,int> test(100);

  test.insert(10,10);
  test.insert(20,20);
  test.insert(5,5);
  test.insert(7,7);
  test.insert(15,15);
  test.insert(2,2);
  test.insert(12,12);

  while (!test.empty()) {
    cout << test.min() << '\n';
    test.removeMin();
  }

  return 0;
}