# 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:

• make-heap1(x)
- creates and returns a leftist heap with a single element x
• insert(h, x)
- inserts element x into heap h
• min(h)
- returns the smallest element currently in the heap h
• remove-min(h)
- similarly to the above returns the smallest element in the heap h, but also removes it from the heap
• make-heap(S)
- creates and returns a leftist heap containing all elements in set
S

• merge(h1, h2)
- merges leftist heaps h1 and h2 into a single leftist heap, which is returned by the function
• merge-queue( Q )
- merges leftist heaps in a non-empty queue Q; esp. useful for lazy heaps below, but also used in make-heap above

#### Lazy leftist heap functions:

• lazy-merge(h1, h2)
- merges leftist heaps h1 and h2 into a single leftist heap, which is returned by the function
• lazy-delete(h, p)
- marks element which is pointed at by pointer p as deleted; this is trivial, so no pseudo-code provided
• lazy-remove-min(h)
- just like the remove-min above, but works even if there are dummy nodes in the heap
• lazy-min(h)
- just like the min above, but works even if there are dummy nodes in the heap

### 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