CS-330: Algorithms

Leftist Heaps pseudo-code

These are my versions of the algorithms, which may be slightly different from the book's.

The leftist heap data structure is defined by the following procedures/methods.

The standard heap functions:

Additional heap function:

Lazy leftist heap functions:

 


make-heap1(x):

Input:     element x
Output:  leftist heap containig a single element x

Algorithm:

left(ptr)
right (ptr)
key
rank (int)

// Let object node contain fields left, right, key, rank
// (first two are pointers and last is an integer)

h <-- new node

h.left <-- NIL; h.right <-- NIL;

h.key <-- x

h.rank <-- 1

return h


insert(h,x):

Input:     heap h, value x
Output:  x is inserted into heap h

Algorithm:

return merge( h, make-heap1(x) )


min(h):

Input:     heap h
Output:  returns the smallest element in h

Algorithm:

return h.key


remove-min(h):

Input:     heap h
Output:  returns the smallest element in h, and removes it from the heap

Algorithm:

x <-- min(h) // this form turns out to be useful for adding lazy deletions later

h <-- merge( h.left, h.right )

return x


make-heap(S):

Input:     List S of elements
Output:  leftist heap containig a single element x

Algorithm:

// Assume standard queue data structure Q

// Put all elements of S into queue Q, making each into a heap first

forall x in S
    Q.enqueue( makeheap1(x) )

return merge-queue( Q )


merge-queue(Q):

Input:     Non-empty queue Q containing leftist heaps
Output:  leftist heap resulting from merging all the queues in Q

Algorithm:

// merge heaps in Q till there is exactly 1 left
// this order of meriging (below) keeps heaps sizes "similar",
// which results in better performance - O(n)

while Q.size > 1 do

h1 <-- Q.deque
h2 <-- Q.deque

Q.enqueue( merge(h1,h2) )

return Q.dequeue


Most of the above functions used merge(.,.) in their implementation - thus merge is not an "added luxury" for this data structure but the basic operation. So, here it is:

merge(h1,h2):

Input:     two leftist heaps h1 and h2
Output:  leftist heaps resulting from the merge of h1 and h2

Algorithm:

// make sure that the root of h1 is ot larger than the root of h2
if h1.key > h2.key then swap(h1,h2)

// now, root of h1 is the root of the merged heap; merge the rest of h1 with h2

if h1.right=nil
    then h1.right <-- h2
    else h1.right <-- merge( h1.right, h2 )

// make sure the leftis property is preserved: rank of left >= rank of right
// assume rank of nil to be 0 - all leaves are nil-nodes
if h1.left.rank < h1.right.rank
    then swap( h1.left, h1.right )

// adjust rank of the root - since rank of right child is never greater than left,
// it is 1+rank of right child
h1.rank <-- h1.right.rank + 1

return h1


lazy-merge(h1,h2):

Input:     two leftist heaps h1 and h2
Output:  leftist heaps resulting from the merge of h1 and h2, but the root is now dummy

Algorithm:

h <-- new node

if h1.rank < h2.rank then swap(h1,h2)

h.left <-- h1

h.right <-- h2

h.rank <-- h.right.rank + 1

return h1


remove-min(h):

Input:     heap h
Output:  returns the smallest element in h, and removes it from the heap; works with dummy nodes

note, how details of lazy operations are hidden away and this function look almost identical to the regular remove-min()

Algorithm:

x <-- lazy-min(h)

h <-- lazy-merge( h.left, h.right )

return x


lazy-min(h):

Input:     heap h
Output:  returns the smallest element in h; works with dummy nodes

Algorithm:

// collect all non-dummy nodes which have only dummies between them and the root
// and store them into a queue Q
collect-nondummies( Q )

h <-- merge-queue(Q)
   // the dummy nodes in the right paths can be either removed by invoking min,
   // or given appropriate values for comparissons

return h.key