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.

**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*(S)**make-heap**S

- creates and returns a leftist heap containing all elements in set

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

**Input: ** element x

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

**Algorithm:**

left(ptr)right(ptr)keyrank(int)

// Let objectnodecontain fieldsleft,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

returnh

**Input: ** heap h,
value x

**Output: ** x is inserted
into heap h

**Algorithm:**

returnmerge( h, make-heap1(x) )

**Input: ** heap h

**Output: ** returns the smallest element in h

**Algorithm:**

returnh.key

**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 laterh <-- merge( h.left, h.right )

returnx

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

forallxinS

Q.enqueue( makeheap1(x) )

returnmerge-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)

whileQ.size > 1doh1 <-- Q.deque

h2 <-- Q.dequeQ.enqueue( merge(h1,h2) )

returnQ.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:

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

ifh1.key > h2.keythenswap(h1,h2)

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

ifh1.right=nil

thenh1.right <-- h2

elseh1.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

ifh1.left.rank < h1.right.rank

thenswap( h1.left, h1.right )

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

// it is 1+rank of right child

returnh1

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

ifh1.rank < h2.rankthenswap(h1,h2)h.left <-- h1

h.right <-- h2

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

returnh1

**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 )

returnx

**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 rootcollect-nondummies( Q )

// and store them into a queue 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

returnh.key