Randomized meldable heap in C. (dynamic/pointer-based tree) https://en.wikipedia.org/wiki/Randomized_meldable_heap

heap.c

#include <stdio.h>
#include <stdlib.h>
#define pf printf

#define nodeptr struct node_t*

struct node_t {
	int val;
	nodeptr rr;
	nodeptr ll;
};

nodeptr heap;

nodeptr new_node(int val) {
	nodeptr x
	= (nodeptr)malloc(sizeof(struct node_t));
	x->val = val; x->ll = NULL; x->rr = NULL;
	return x;
}

////////////////////////////////////////////////////////////////////////////////

nodeptr meld(nodeptr a, nodeptr b) {
	if (a == NULL) return b;
	if (b == NULL) return a;
	if (a->val > b->val)
		{ nodeptr t = a; a = b; b = t; }
	if (rand() & 1) a->ll = meld(a->ll, b);
	else            a->rr = meld(a->rr, b);
	return a;
}

void push(int x)
	{ heap = meld(new_node(x), heap); }

void pop(void)
	{ heap = meld(heap->ll, heap->rr); }

int top(void)
	{ return heap->val; }

////////////////////////////////////////////////////////////////////////////////

int main() {
	heap = NULL;

	int vals[10] = {100, 20, 30, 40, 15, 25, 2, 3, 200, 150};
	//              2    3   15  20  25  30 40 100 150  200   (SORTED)

	printf("=== @1: CASE ===\n");
	for (int i = 0; i < 10; i++)
		{ push(vals[i]); pf("push = %3d; min_heap = %3d;\n", \
			vals[i], top()); }
	
	printf("=== @2: CASE ===\n");
	for (int i = 0; i < 10; i++)
		{ pf("min_heap = %3d;\n", top()); pop(); }

	return 0;
}

output.txt

=== @1: CASE ===
push = 100; min_heap = 100;
push =  20; min_heap =  20;
push =  30; min_heap =  20;
push =  40; min_heap =  20;
push =  15; min_heap =  15;
push =  25; min_heap =  15;
push =   2; min_heap =   2;
push =   3; min_heap =   2;
push = 200; min_heap =   2;
push = 150; min_heap =   2;
=== @2: CASE ===
min_heap =   2;
min_heap =   3;
min_heap =  15;
min_heap =  20;
min_heap =  25;
min_heap =  30;
min_heap =  40;
min_heap = 100;
min_heap = 150;
min_heap = 200;