On both Wikipedia and the paper it was introduced the randomized meldable heap uses the following procedure to meld two heaps:
function Meld(Node Q1, Node Q2) if Q1 is nil => return Q2 if Q2 is nil => return Q1 if Q1 > Q2 => swap Q1 and Q2 if coin_toss is 0 => Q1.left = Meld(Q1.left, Q2) else Q1.right = Meld(Q1.right, Q2) return Q1
But isn't this oversimplified? We choose recursively to meld with either the left or the right child. But this isn't always necessary, if Q1 has no or one child you can immediately stop the melding process by putting Q2 in the missing spot. I propose this instead:
function Meld(Node Q1, Node Q2) if Q1 is nil => return Q2 if Q2 is nil => return Q1 if Q1 > Q2 => swap Q1 and Q2 if Q1.left is nil => Q1.left = Q2 else if Q1.right is nil => Q1.right = Q2 else if coin_toss is 0 => Q1.left = Meld(Q1.left, Q2) else Q1.right = Meld(Q1.right, Q2) return Q1
I've found experimentally that this reduces the average height by roughly $0.3$ and the maximum height of the tree by roughly $1.3$, both gains seem fairly consistent for various $n$ (I'm seeing the same gains for $n = 10, 10^3, 10^6$) when inserting uniformly random elements.
Am I missing anything? Isn't this just strictly better?
The average and maximum height gains are surprisingly consistently in the neighbourhood of $0.3$ and $1.3$ respectively. Can these values be rigorously justified?