leftist_tree_aux.cpp

// Leftist Tree ( Leftist Heap )
// Thiago Mota

#include <bits/stdc++.h>

using namespace std;

struct node{
	int key, dist;
	node *l, *r;

	node(int key = 0):
		key(key),
		dist(0),
		l(nullptr), r(nullptr)
	{ }
};

inline int dist(node* root){
	if(root) return root->dist;
	return -1;
}

void merge(node*& root, node* l, node* r){
	if(l == nullptr || r == nullptr){
		if(l) root = l;
		else root = r;

		return;
	}

	if(l->key > r->key)
		swap(l, r);

	merge(l->r, l->r, r);

	if(dist(l->r) > dist(l->l))
		swap(l->l, l->r);

	l->dist = dist(l->r) + 1;
	root = l;
}

inline void insert(node*& root, int key){
	node *it = new node(key);
	merge(root, root, it);
}

inline void removeTop(node*& root){
	if(root == nullptr)
		return;

	node* it = root;
	merge(root, root->l, root->r);
	delete it;
}

int main(){
	int n;
	cin >> n;
	node* root = nullptr;
	for(int i=1;i<=n;i++){
		int x;
		cin >> x;
		insert(root, x);
	}

	for(int i=1;i<=n;i++)
		cout << root->key << " \n"[i==n], removeTop(root);
	return 0;
}