---
tags: codebook
---

{%hackmd theme-dark %}

# leftist tree

#include<iostream>
#include<queue>
#include<vector>
#include<cassert>
using namespace std;
template<typename T, typename Compare = std::less<T>>
struct leftist {
	size_t m_size;
	Compare cmp;
	struct node {
		T key;
		int s_val;
		node *left, *right;
		node(const int& x): key(x), s_val(0) {
			left = right = nullptr;
		}
		friend int s(node* x) {return x ? x->s_val : -1;}
	}*root;
	node* merge(node* a, node* b) {
		if (!a || !b) return a ? a : b;
		if (cmp(a->key, b->key)) swap(a, b);
		a->left = merge(a->left, b);
		if (s(a->left) < s(a->right))
			swap(a->left, a->right);
		a->s_val = s(a->right) + 1;
		return a;
	}
	inline void join(leftist& x) {
		root = merge(root, x.root);
		m_size += x.m_size;
		x.m_size = 0, x.root = nullptr;
	}
	inline void pop() {
		if (m_size) m_size--;
		node* tmp = merge(root->left, root->right);
		delete root; root = tmp;
	}
	inline void push(const int& x) {m_size++, root = merge(root, new node(x));}
	inline const T& top() const {assert(m_size); return root->key;}
	void clear(node* x) {if (x) clear(x->left), clear(x->right), delete x;}
	inline void clear() {clear(root), m_size = 0, root = nullptr;}
	inline size_t size() const {return m_size;}
	inline bool empty() const {return !m_size;}
	leftist(const vector<T>& v = {}): m_size(v.size()), root(nullptr) {
		queue<node*> q({nullptr});
		for (const auto& i : v)
			q.push(new node(i));
		while (q.size() != 1) {
			node* a = q.front(); q.pop();
			node* b = q.front(); q.pop();
			q.push(merge(a, b));
		}
		root = q.front();
	}
	~leftist() {clear(root);}
};
int main() {
	leftist<int> tree({1, 5, 4, 2, 3});
	leftist<int> b({6, 8, 7, 9, 0});
	tree.join(b);
	while (tree.size())
		cout << tree.top() << ' ', tree.pop();
	cout << endl;
	return 0;
}