# Homework 3

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 `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 1: Leftist Heaps

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

Define

``fromList : List Int -> Heap``

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 -> List Heap
makePass   : List Heap -> List Heap``````

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 `BinomialHeaps.elm` from class.

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

Submit the three files `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``````

Start by navigating to the folder where you checked out your repo. Next, create a subfolder for this assignment and populate it with the skeleton code:

``````% svn mkdir hw3
% cd hw3
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw3/LHeaps.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw3/BHeaps.elm
% wget http://www.classes.cs.uchicago.edu/current/22300-1/assignments/hw3/ExplicitMin.elm``````

If `wget` or a similar tool (such as `curl`) is not available on your machine, download and save the skeleton files provided above in some other way. Then add only these files to your repo:

``````% svn add LHeaps.elm
``% svn commit -m "hw3 submission"``
``https://phoenixforge.cs.uchicago.edu/projects/USER-cs223-win-16/repository``