1
$\begingroup$

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.

Two questions:

  1. Am I missing anything? Isn't this just strictly better?

  2. 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?

$\endgroup$
  • $\begingroup$ The goal of the paper was to present a meldable heap in which the height is logarithmic with high probability. You are suggesting a quantitative improvement. Your improvement, if any, only affects constant factors. $\endgroup$ – Yuval Filmus Jul 23 '18 at 14:10
  • $\begingroup$ You can try to rigorously analyze both algorithms, using a specific random scenario (presumably, they same one you used to empirically test the procedures). $\endgroup$ – Yuval Filmus Jul 23 '18 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.