The implicit representation of a complete binary tree as an array,
or list, seems to have been first proposed by Eytzinger [27].
He used this representation in books containing pedigree family trees
of noble families. The
data structure described here was
first introduced by Williams [76].

The randomized
data structure described here appears
to have first been proposed by Gambin and Malinowski [34].
Other meldable heap implementations exist, including
leftist heaps [16,48, Section 5.3.2],
binomial heaps [73],
Fibonacci heaps [30],
pairing heaps [29], and skew heaps [70],
although none of these are as simple as the
structure.

Some of the above structures also support a
operation
in which the value stored at node
is decreased to
. (It is a
pre-condition that
.) In most of the preceding structures,
this operation can be supported in
time by removing node
and adding
. However, some of these structures can implement
more efficiently. In particular,
takes amortized time in Fibonacci heaps and
amortized time in a special version of pairing heaps [25].
This more efficient
operation has applications in
speeding up several graph algorithms, including Dijkstra's shortest path
algorithm [30].

**Exercise 10..1**
Illustrate the addition of the values 7 and then 3 to the

shown at the end of Figure

10.2.

**Exercise 10..2**
Illustrate the removal of the next two values (6 and 8) on the

shown at the end of Figure

10.3.

**Exercise 10..3**
Implement the

method, that removes the value stored in

in a

. This method should run in

time.
Next, explain why this method is not likely to be useful.

**Exercise 10..4**
A

-ary tree is a generalization of a binary tree in which each
internal node has

children. Using Eytzinger's method it is also
possible to represent complete

-ary trees using arrays. Work out
the equations that, given an index

, determine the index of

's
parent and each of

's

children in this representation.

**Exercise 10..5**
Using what you learned in Exercise

10.4, design and
implement a

, the

-ary generalization of a

. Analyze the running times of operations on a

and test the performance of your

implementation against
that of the

implementation given here.

**Exercise 10..6**
Illustrate the addition of the values 17 and then 82 in the

shown in Figure

10.4. Use a coin to
simulate a random bit when needed.

**Exercise 10..7**
Illustrate the removal of the next two values (4 and 8) in the

shown in Figure

10.4. Use a coin to
simulate a random bit when needed.

**Exercise 10..8**
Implement the

method, that removes the node

from
a

. This method should run in

expected time.

**Exercise 10..9**
Show how to find the second smallest value in a

or

in constant time.

**Exercise 10..10**
Show how to find the

th smallest value in a

or

in

time. (Hint: Using another heap
might help.)

**Exercise 10..11**
Suppose you are given

sorted lists, of total length

. Using
a heap, show how to merge these into a single sorted list in

time. (Hint: Starting with the case

can be instructive.)

opendatastructures.org