# Lab 4 (140 points)

The goal of this assignment is to develop further experience with the heap data structures in Chapter 3 of the Okasaki textbook. Download the skeleton files `THeaps.elm`, `LHeaps.elm`, `BHeaps.elm`, and `ExplicitMin.elm`, and use them as a starting point for the following problems. Look for all occurrences of `TODO` in comments, which point out where you should implement your solutions. Once you are done, follow the submission instructions below.

## Problem 0: Heaps as Complete Binary Trees

We saw how to implement min-heaps using the `Array` library in the Heaps lecture. Now, you’ll implement the same complete binary tree approach using trees directly, rather than `Array`s.

Download the skeleton file `THeaps.elm` and use it as a starting point for this problem. Look for all occurrences of `TODO` in comments, which point out where you should implement your solutions.

We’ll use the same definition of `Tree` from before:

``type Tree a = Empty | Node a (Tree a) (Tree a)``

A heap will be represented as a complete binary `Tree` along with its size (the number of `Node`s in the `Tree`):

``type Heap a = Heap (Int, Tree a)``

You will implement all operations of the min-heap abstraction except for `merge`.

### Helper Functions

Recall the modular arithmetic used to traverse between parent and child nodes:

``````parentIndex i = (i-1) // 2

leftIndex i   = (2*i) + 1
rightIndex i  = (2*i) + 2``````

To help factor the algorithms below, we first define the notion of a path from the root of a `Tree` to the subtree at position `i` (according to the 0-based, breadth-first indexing scheme from Heaps):

``````type Dir = Left | Right

pathTo : Int -> List Dir
pathTo =
let foo i =
if i == 0 then []
else if rem i 2 == 1 then Left :: foo (parentIndex i)
else Right :: foo (parentIndex i)
in
List.reverse << foo``````

For example:

``````> import THeaps exposing (..)

> pathTo 0
[] : List THeaps.Dir

> pathTo 1
[Left] : List THeaps.Dir

> pathTo 2
[Right] : List THeaps.Dir

> pathTo 3
[Left,Left] : List THeaps.Dir

> pathTo 10
[Left,Right,Right] : List THeaps.Dir

> pathTo 58
[Right,Right,Left,Right,Right] : List THeaps.Dir``````

#### 4.0.1 — Basic Operations (10 points)

First, implement the following `Heap` operations:

``````empty : Heap comparable
isEmpty : Heap comparble -> Bool
findMin : Heap comparable -> Maybe comparable``````

#### 4.0.2 — Insertion (20 points)

Next, implement the `insert` operation:

``insert : comparable -> Heap comparable -> Heap comparable``

You may consider using the helper functions above, but you are free to implement `insert` however you wish.

Spoiler Alert: There are hints below.

#### 4.0.3 — Deletion (20 points)

Finally, implement the `deleteMin` operation:

``deleteMin : Heap comparable -> Maybe (comparable, Heap comparable)``

Again, you may consider using the helper functions above, but you are free to implement `insert` however you wish.

Spoiler Alert: There are more hints below.

## Problem 1: Leftist Heaps

#### 3.1.1 — Okasaki, Exercise 3.3 (30 points)

Define

``fromList : List comparable -> Heap comparable``

such that `fromList xs` turns an unordered list `xs` into a `Heap` by making O(log n) passes over the list `xs`, pairwise merging adjacent elements. In comments, explain why your solution runs in O(n) time, where n is the length of `xs`.

Hint: one strategy is to factor the solution into two helper functions

``````mergePairs : List (Heap comparable) -> List (Heap comparable)
makePass   : List (Heap comparable) -> List (Heap comparable)``````

where `mergePairs` calls `merge` on adjacent pairs of elements, and `makePass` makes another pass over the list to merge pairs if necessary and otherwise returns the final result.

To analyze the worst-case running time for such an implementation, define two recurrence relations such that

• S(n,m) is the time that `mergePairs hs` takes, where n is the length of `hs` and m is the size of the largest heap in `hs`, and
• T(n,m) is the time that `makePass hs` takes, where n is the length of `hs` and m is the size of the largest heap in `hs`.

## Problem 2: Binomial Heaps

#### 3.2.1 — Okasaki, Exercise 3.6 (30 points)

This problem proposes an alternative representation of binomial heaps that eliminates redundant rank information. Reimplement binomial heaps with this new representation in `BHeaps.elm`, so that the operations have the same running times as in the original implementation.

#### 3.2.2 — Okasaki, Exercise 3.7 (30 points)

The implementation of binomial heaps we have seen provides O(log n) access to the minimum element rather than O(1) time as for leftist heaps. In this problem, you will implement a “wrapper” module `ExplicitMin` that imports an implementation of the heap abstraction and exports an implementation of the heap abstraction that provides O(1) time access to the minimum element.

The problem in the textbook uses ML functors to abstract this pattern in order to work with any implementation of heaps (not just binomial heaps). Because Elm does not support ML-style modules or Haskell-style type clases, we will hard-code our solution to work with binomial heaps.

Implement the heap abstraction in `ExplicitMin.elm` so that `findMin` runs in O(1) time and the remaining operations have the same O(log n) running times as those in `BinomialHeap.elm` from class.

While you are developing and testing your code, you will need to place `BinomialHeap.elm` in the same directory as your solution (but you will not submit it).

Submit the four files `THeaps.elm`, `LHeaps.elm`, `BHeaps.elm`, and `ExplicitMin.elm` updated with your changes. You are free to modify these files as you wish, as long as you do not change any type signatures that are provided.

Your solution will be graded using a combination of automated grading scripts and manual review. It is a good idea for you to design some test cases of your own to exercise more sample behaviors than just the ones provided in the writeup. We also reserve the right to take into account the organization and style of your code when assigning grades.

If you are not able to finish all parts of the assignment, make sure that all of your submitted files compile successfully. If not, you risk getting zero points for the assignment. In particular, for each file `Foo.elm`, make sure that it can be loaded into the Elm REPL

``````% elm-repl
> import Foo
>``````

and that it can be compiled to a standalone HTML file:

``````% elm-make Foo.elm --output=Foo.html
Successfully generated Foo.html``````

# Hints

#### 4.0.2 and 4.0.3

One option for `insert` is to start with the following and define the helper function `insertAndBubbleUp`.

``````insert x (Heap (n, t)) =
if n == 0
then Heap (1, Node x Empty Empty)
else Heap (1 + n, insertAndBubbleUp x (pathTo (parentIndex n)) t)

insertAndBubbleUp : comparable -> List Dir -> Tree comparable -> Tree comparable``````

One option for `deleteMin` is to start with the following and define the helper functions `removeElement` and `bubbleDown`.

``````deleteMin (Heap (n, t)) =
case t of
Empty -> Nothing
Node x Empty Empty -> Just (x, empty)
Node x _ _ ->
let (lastElement, newTree) = removeElement (pathTo (n-1)) t in
case newTree of
Empty -> Debug.crash "deleteMin: impossible"
Node _ left right ->
Just (x, Heap (n - 1, bubbleDown (Node lastElement left right)))

removeElement : List Dir -> Tree comparable -> (comparable, Tree comparable)

bubbleDown : Tree comparable -> Tree comparable``````