/*
  Copyright 2013 Marek "p2004a" Rusinowski
  Leftist Heap
*/
#include <cstdio>
#include <cstdlib>
#include <ctime>

#include <algorithm>
#include <functional>

using namespace std;

template <class T, class Compare = less<T> >
class LeftistHeap {
 public:
  class LeftistHeapNode {
   public:
    T value;
    LeftistHeapNode *left, *right;
    int s;
    
    LeftistHeapNode(T vvalue, LeftistHeapNode *lleft, LeftistHeapNode *rright, int ss)
     : value(vvalue), left(lleft), right(rright), s(ss) {}
     
    LeftistHeapNode(const LeftistHeapNode &node) : value(node.value), left(NULL), right(NULL), s(node.s) {
      if (node.left != NULL) left = new LeftistHeapNode(*node.left);
      if (node.right != NULL) right = new LeftistHeapNode(*node.right);
    }
     
    ~LeftistHeapNode() {
      delete left;
      delete right;
    }
  };
  
  LeftistHeapNode *merge(LeftistHeapNode *h1, LeftistHeapNode *h2) {
    if (h1 == NULL) return h2;
    if (h2 == NULL) return h1;
    if (!cmp(h1->value, h2->value)) swap(h1, h2);
    if (h1->left == NULL) h1->left = h2;
    else {
      h1->right = merge(h1->right, h2);
      if (h1->left->s < h1->right->s) swap(h1->left, h1->right);
      h1->s = h1->right->s + 1;
    }
    return h1;
  }
  
 private:
  LeftistHeapNode *root;
  size_t heap_size;
  Compare cmp;
  
 public:
  LeftistHeap() : root(NULL), heap_size(0) {}
  
  LeftistHeap(const LeftistHeap &heap) : root(NULL), heap_size(heap.heap_size) {
    if (heap.root != NULL) root = new LeftistHeapNode(*heap.root);
  }
  
  ~LeftistHeap() {
    delete root;
  }
  
  LeftistHeap &operator=(const LeftistHeap &heap) {
    delete root;
    root = new LeftistHeapNode(*heap.root);
    heap_size = heap.heap_size;
    return *this;
  }
  
  LeftistHeapNode *insert(T value) {
    LeftistHeapNode *node = new LeftistHeapNode(value, NULL, NULL, 0);
    root = merge(root, node);
    ++heap_size;
    return node;
  }
  
  T top() {
    if (root == NULL) throw "Cannot get min from empty heap";
    return root->value;
  }
  
  T deltop() {
    if (root == NULL) throw "Cannot del min from empty heap";
    LeftistHeapNode *tmp = root;
    root = merge(root->left, root->right);
    --heap_size;
    tmp->left = tmp->right = NULL;
    T value = tmp->value;
    delete tmp;
    return value;
  }
  
  void merge(LeftistHeap &heap) {
    root = merge(root, heap.root);
    heap_size += heap.heap_size;
    heap.root = NULL;
    heap.heap_size = 0;
  }
  
  size_t size() {
    return heap_size;
  }
};

inline int los(int a, int b) {
  return rand() % (b - a + 1) + a;
}

int main() {
  srand(time(NULL));
  LeftistHeap<int> heap1, heap2, heap3;
  int n = 20;
  for (int i = 0; i < n; ++i) {
    heap1.insert(los(1, 200));
    heap2.insert(los(1, 200));
  }
  heap3 = heap2;
  heap1.merge(heap2);
  heap1.merge(heap3);
  while (heap1.size() > 0) {
    printf("%d ", heap1.deltop());
  }
  printf("\n");
  return 0;
}