This chapter and Chapter 21 present data structures known as * mergeable heaps*, which support the following five operations.

MAKE-HEAP() creates and returns a new heap containing no elements.

INSERT(*H, x*) inserts node *x*, whose *key* field has already been filled in, into heap *H*.

MINIMUM(*H*) returns a pointer to the node in heap *H* whose key is minimum.

EXTRACT-MIN(*H*) deletes the node from heap* H* whose key is minimum, returning a pointer to the node.

UNION(*H*_{l},* H*_{2}) creates and returns a new heap that contains all the nodes of heaps *H*_{1} and *H*_{2}. Heaps *H*_{1} and *H*_{2} are "destroyed" by this operation.

In addition, the data structures in these chapters also support the following two operations.

DECREASE-KEY(*H, x, k*) assigns to node *x* within heap *H* the new key value *k*, which is assumed to be no greater than its current key value.

DELETE(*H, x*) deletes node *x* from heap *H*.

In Chapter 21, we shall explore Fibonacci heaps, which have even better time bounds for some operations. Note, however, that the running times for Fibonacci heaps in Figure 20.1 are amortized time bounds, not worst-case per operation time bounds.

Binary heap Binomial heap Fibonacci heap

Procedure (worst-case) (worst-case) (amortized)

--------------------------------------------------------------

MAKE-HEAP (1) (1) (1)

INSERT (lgn)O(lgn) (1)

MINIMUM (1)O(lgn) (l)

EXTRACT-MIN (lgn) (1gn)O(lgn)

UNION (n)O(lgn) (1)

DECREASE-KEY (lgn) (lgn) (1)

DELETE (1gn) (lgn)O(lgn)

The **binomial tree ***B _{k}* is an ordered tree (see Section 5.5.2) defined recursively. As shown in Figure 20.2(a), the binomial tree

Some properties of binomial trees are given by the following lemma*.*

2. the height of the tree is *k*,

3. there are exactly nodes at depth *i* for *i* = 0, 1, . . . , *k*, and

4. the root has degree *k*, which is greater than that of any other node; moreover if the children of the root are numbered from left to right by* k* - 1, *k* - 2, . . . ,* *0, child *i* is the root of a subtree *B _{i}*.

For the inductive step, we assume that the lemma holds for *B _{k}*-1.

The maximum degree of any node in an *n*-node binomial tree is lg *n*.

* Proof *Immediate from properties l and 4 of Lemma 20.1.

A * binomial heap H* is a set of binomial trees that satisfies the following

1. Each binomial tree in *H* is* heap-ordered:* the key of a node is greater than or equal to the key of its parent.

2. There is at most one binomial tree in *H* whose root has a given degree.

As Figure 20.3 also shows, the roots of the binomial trees within a binomial heap are organized in a linked list, which we refer to as the * root list*. The degrees of the roots strictly increase as we traverse the root list. By the second binomial-heap property, in an

To make an empty binomial heap, the MAKE-BINOMIAL-HEAP procedure simply allocates and returns an object *H*, where *head*[*H*] = NIL. The running time is (1).

The procedure BINOMIAL-HEAP-MINIMUM returns a pointer to the node with the minimum key in an *n*-node binomial heap *H*. This implementation assumes that there are no keys with value . (See Exercise 20.2-5.)

BINOMIAL-HEAP-MINIMUM(H)

1yNIL

2xhead[H]

3min

4whilexNIL

5do ifkey[x] <min

6thenminkey[x]

7yx

8xsibling[x]

9returny

The operation of uniting two binomial heaps is used as a subroutine by most of the remaining operations. The BINOMIAL-HEAP-UNION procedure repeatedly links binomial trees whose roots have the same degree. The following procedure links the *B _{k}*-1 tree rooted at node

BINOMIAL-LINK(y,z)

1p[y]z

2sibling[y]child[z]

3child[z]y

4degree[z]degree[z]+1

Figure 20.5 shows an example of BINOMIAL-HEAP-UNION in which all four cases given in the pseudocode occur.

The BINOMIAL-HEAP-UNION procedure has two phases. The first phase, performed by the call of BINOMIAL-HEAP-MERGE, merges the root lists of binomial heaps *H*_{1} and *H*_{2} into a single linked list *H* that is sorted by degree into monotonically increasing order. There might be as many as two roots (but no more) of each degree, however, so the second phase links roots of equal degree until at most one root remains of each degree. Because the linked list *H* is sorted by degree, we can perform all the link operations quickly.

*x* points to the root currently being examined,

*prev-x* points to the root preceding *x* on the root list: *sibling*[*prev-x*] = *x*, and

*next-x* points to the root following *x* on the root list: *sibling*[*x*] = *next-x*.

degree[x] =degree[next-x]=degree[sibling[next-x]].

Cases 3 and 4 occur when *x* is the first of two roots of equal degree, that is, when

degree[x] =degree[next-x]degree[sibling[next-x]].

The following procedure inserts node *x* into binomial heap *H,* assuming of course that node *x* has already been allocated and *key*[*x*] has already been filled in.

BINOMIAL-HEAP-INSERT(H,x)

1H'MAKE-BINOMIAL-HEAP()

2p[x] NIL

3child[x] NIL

4sibling[x] NIL

5degree[x] 0

6head[H'] x

7HBINOMIAL-HEAP-UNION(H,H')

The following procedure extracts the node with the minimum key from binomial heap *H* and returns a pointer to the extracted node.

BINOMIAL-HEAP-EXTRACT-MIN(H)

1 find the rootxwith the minimum key in the root list ofH,

and removexfrom the root list ofH

2H' MAKE-BINOMIAL-HEAP()

3 reverse the order of the linked list ofx's children,

and sethead[H'] to point to the head of the resulting list

4H_{ BINOMIAL-HEAP-UNION(H,H}')

5returnx

The following procedure decreases the key of a node *x* in a binomial heap *H* to a new value *k*. It signals an error if *k* is greater than *x*'s current key.

BINOMIAL-HEAP-DECREASE-KEY (H,x,k)

1ifk>key[x]

2then error"new key is greater than current key"

3key[x]k

4yx

5zp[y]

6whilezNIL andkey[y] <key[z]

7doexchangekey[y]key[z]

8 Ifyandzhave satellite fields, exchange them, too.

9yz

10zp[y]

It is easy to delete a node *x'*s key and satellite information from binomial heap *H* in *O*(lg* n*) time. The following implementation assumes that no node currently in the binomial heap has a key of - .

BINOMIAL-HEAP-DELETE(H,x)

1 BINOMIAL-HEAP-DECREASE-KEY(H,x,-)

2 BINOMIAL-HEAP-EXTRACT-MIN(H)

The BINOMIAL-HEAP-DELETE procedure takes *O*(lg *n*) time.

Write pseudocode for BINOMIAL-HEAP-MERGE.

Explain why the BINOMIAL-HEAP-MINIMUM procedure might not work correctly if keys can have the value . Rewrite the pseudocode to make it work correctly in such cases.

Suppose there is no way to represent the key - . Rewrite the BINOMIAL-HEAP-DELETE procedure to work correctly in this situation. It should still take *O*(lg *n*) time.

Discuss the relationship between inserting into a binomial heap and incrementing a binary number and the relationship between uniting two binomial heaps and adding two binary numbers.

In light of Exercise 20.2-7, rewrite BINOMIAL-HEAP-INSERT to insert a node directly into a binomial heap without calling BINOMIAL-HEAP-UNION.

Chapter 19 introduced the 2-3-4 tree, in which every internal node (other than possibly the root) has two, three, or four children and all leaves have the same depth. In this problem, we shall implement **2-3-4 heaps***,* which support the mergeable-heap operations.

**a****.** MINIMUM, which returns a pointer to the leaf with the smallest key.

**b****.** DECREASE-KEY, which decreases the key of a given leaf *x* to a given value *k* *key*[*x*].

**c.** INSERT, which inserts leaf *x* with key *k*.

**d****.** DELETE, which deletes a given leaf *x*.

**e****.** EXTRACT-MIN, which extracts the leaf with the smallest key.

* f.* UNION, which unites two 2-3-4 heaps, returning a single 2-3-4 heap and destroying the input heaps.

20-2 Minimum-spanning-tree algorithm using mergeable heaps

Chapter 24 presents two algorithms to solve the problem of finding a minimum spanning tree of an undirected graph. Here, we shall see how mergeable heaps can be used to devise a different minimum-spanning-tree algorithm.

E{(_{i}u,v):uVor_{i}vV}_{i}

of edges incident on vertices in *V _{i}*.

Describe how to implement this algorithm using the mergeable-heap operations given in Figure 20.1. Give the running time of your implementation, assuming that the mergeable heaps are implemented by binomial heaps.