Some Familiar Data Structures in a Functional Setting

Prev: Persistence Next: Lazy Evaluation

Prev: Persistence Next: Lazy Evaluation

3.1 Leftist Heaps

Exercises

Exercise 3.1

Prove that the right spine of a leftist heap of size $n$ contains at most $\lfloor \log (n+1)\rfloor$ elements. All logarithms in this book are base 2 unless otherwise indicated.

Exercise 3.2

Define insert directly rather than via a call to merge.

Exercise 3.3

Implement a function fromList of type Elem.T list -> Heap that produces a leftist heap from an unordered list of elements by first converting each element into a singleton heap and then merging the heaps until only one heap remains.

Instead of merging the heaps in one right-to-left or left-to-right pass using foldr or foldl, merge the heaps in $\lfloor \log n\rfloor$ passes, where each pass merges adjacent pairs of heaps. Show that fromList takes only $O(n)$ time.

Exercise 3.4

Weight-biased leftist heaps are an alternative to leftist heaps that replace the leftist property with the weight-biased leftist property: the size of any left child is at least as large as the size of its right sibling.

1. Prove that the right spine of a weight-biased leftist heap contains at most $\lfloor \log (n+1)\rfloor$ elements.
2. Modify the implementation in Figure 3.2 to obtain weight-biased leftist heaps.
3. Currently, merge operates in two passes: a top-down pass consisting of calls to merge, and a bottom-up pass consisting of calls to the helper function makeT. Modify merge for weight-biased leftist heaps to operate in a single, top-down pass.
4. What advantages would the top-down version of merge have in a lazy environment? In a concurrent environment?

3.2 Binomial Heaps

Exercises

Exercise 3.5

Define findMin directly rather than via a call to removeMinTree.

Exercise 3.6

Most of the rank annotations in this representation of binomial heaps are redundant because we know that the children of a node of rank $r$ have ranks $r-1,\dots ,0$. Remove the rank annotations from each node and instead pair each top-level tree with its rank:

datatype Tree = Node of Elem x Tree list
type Heap = (int * Tree) list

Reimplement binomial heaps with this new representation.

Exercise 3.7

One clear advantage of leftist heaps over binomial heaps is that findMin takes only $O(1)$ time rather than $O(\log n)$ time. The following functor skeleton improves the running time of findMin to $O(1)$ by storing the minimum element separately from the rest of the heap:

functor ExplicitMin (H : HEAP) : HEAP =
struct
  structure Elem = H.Elem
  datatype Heap = E | NE of Elem.T * H.Heap
end

Complete this functor so that findMin takes $O(1)$ time, and insert, merge, and deleteMin take $O(\log n)$ time, assuming that all four take $O(\log n)$ time or better for the underlying implementation H.

3.3 Red-Black Trees

Exercises

Exercise 3.8

Prove that the maximum depth of a node in a red-black tree of size $n$ is at most $2\lfloor \log (n+1)\rfloor$.

Exercise 3.9

Write a function fromOrdList of type Elem list -> Tree that converts a sorted list with no duplicates into a red-black tree. Your function should run in $O(n)$ time.

Exercise 3.10

The balance function currently performs several unnecessary tests. For example, when the ins function recurses on the left child, there is no need for balance to test for red-red violations involving the right child.

1. Split balance into two functions, lbalance and rbalance, that test for violations involving the left child and right child, respectively. Replace the calls to balance in ins with calls to either lbalance or rbalance.
2. Extending the same logic one step further, one of the remaining tests on the grandchildren is also unnecessary. Rewrite ins so that it never tests the color of nodes not on the search path.

3.4 Chapter Notes