leftist_tree.cpp

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

#include <bits/stdc++.h>

using namespace std;

template<typename type>
class lheap{
public:
	struct node{
		type key;
		uint32_t dist;
		node *l, *r;
		node(type key = type()): key(key), dist(0), l(nullptr), r(nullptr) { }
	};

	uint32_t dist(node* root){
		return root ? root->dist : 0;
	}

	void merge(node*& root, node* l, node* r){
		if(l == nullptr || r == nullptr){
			root = l ? l : 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;
	}

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

	void removeTop(node*& root){
		if(root == nullptr) return;
		node* it = root;
		merge(root, root->l, root->r);
		delete it;
	}
	
	node *root;
public:
	lheap():
		root(nullptr) { }

	~lheap(){
		if(root) delete root;
	}

	type const& top() const{
		return root->key;
	}

	bool empty() const{
		return (root == nullptr);
	}

	void push(type const& key){
		insert(root, key);
	}

	void pop(){
		removeTop(root);
	}

	static lheap merge(lheap& lhs, lheap& rhs){
		lheap aux;

		aux.merge(aux.root, lhs.root, rhs.root);

		lhs.root = rhs.root = nullptr;

		return aux;
	}
};

template<typename T>
inline lheap<T> merge(lheap<T>& lhs, lheap<T>& rhs){
	return lheap<T>::merge(lhs, rhs);
}

int main(){
	int n, m;
	cin >> n >> m;
	lheap<int> pq1, pq2;

	for(int i=1;i<=n;i++){
		int x;
		cin >> x;
		pq1.push(x);
	}
	for(int i=1;i<=m;i++){
		int x;
		cin >> x;
		pq2.push(x);
	}

	auto pq = merge(pq1, pq2);

	while(!pq.empty())
		cout << pq.top() << " ", pq.pop();
	cout << "\n";
	
	return 0;
}