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