The implicit representation of a complete binary tree as an array,
or list, seems to have been first proposed by Eytzinger [27],
as a representation for pedigree family trees. The `BinaryHeap` data
structure described here was first introduced by Williams [76].

The randomized `MeldableHeap` 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 [32], pairing heaps [31], and skew heaps
[70], although none of these are as simple as the `MeldableHeap`
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
.) This operation can be implemented
in
time in most of the above structures 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 [32].

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

`BinaryHeap`
shown at the end of Figure

10.2.

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

`BinaryHeap` shown at the end of Figure

10.3.

**Exercise 10..3**
Implement the

method, that removes the value stored in

in a

`BinaryHeap`. 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

`DaryHeap`, the

-ary generalization of a

`BinaryHeap`. Analyze the running times of operations on a

`DaryHeap`
and test the performance of your

`DaryHeap` implementation against
that of the

`BinaryHeap` implementation given here.

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

`MeldableHeap`
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

`MeldableHeap`
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

`MeldableHeap`. This method should run in

expected time.

**Exercise 10..9**
Show how, in a `BinaryHeap` or `MeldableHeap`, to find the second
smallest value in constant time.

**Exercise 10..10**
Show how, in a

`BinaryHeap` or

`MeldableHeap`, to find the

th
smallest value in

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

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

sorted lists, of total length

. Show how,
using a heap, to merge these into a single sorted list in

time. (Hint: Starting with the case

can be instructive.)

opendatastructures.org