R < = |_ lg (N + 1) _|
Meld (H1, H2)
{
if (rootValue
( H1 ) > rootValue ( H2 )
or (root
( H1 ) is NULL
swap ( H1, H2 )
if ( root (
H1 ) is not NULL )
{
right ( H1 ) = Meld ( right ( H1), H2 )
if ( leftLength ( H1 ) < rightLength ( H1 )
swap ( left ( H1 ), right ( H1 ) )
{
return H1
}
clever approach --- use a queue and build
heap "pair-wise"
{
make N 1-vertex
LHs
Queue Q;
for ( i = 1;
i <= N; i++ )
Q.Enqueue ( Hi )
Heap H = Q.Dequeue ( );
while ( ! Q.IsEmpty
( ) )
{
Q.Enqueue ( Meld (H, Q.Dequeue ( ) );
H = Q.Dequeue ( );
}
}