Meldable Heap Implementation

meldable_heap.cpp

#include <bits/stdc++.h>

using namespace std;

template<typename T>
struct mheap
{
	struct node
	{
		T val;
		node *l, *r;

		node(T val)
			: val(val), l(nullptr), r(nullptr) {};
	};

	node *t;
	mt19937 rd;
	uniform_int_distribution<int> toss;

	mheap()
	{
		t = nullptr;
		toss = uniform_int_distribution<int>(0,1);
	}

	node* meld(node *l, node *r)
	{
		if (!l) return r;
		if (!r) return l;

		if (l->val < r->val) swap(l, r);

		if (toss(rd)) l->l = meld(l->l, r);
		else l->r = meld(l->r, r);

		return l;
	}

	void push(T x)
	{
		node *aux = new node(x);
		t = meld(t, x);
	}

	void pop()
	{
		t = meld(t->l, t->r);
	}

	T top()
	{
		return t->val;
	}

	void merge(mheap x)
	{
		t = meld(t, x->t);
	}
};