The goal of this assignment is to develop further experience with the heap data structure in Chapter 3 of the Okasaki textbook.
Elm Test: You are strongly encouraged to write tests for your solutions, though you are not required to submit them.
(This problem really is optional. Do the rest first.)
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 Arrays (wrappers around imperative JavaScript arrays).
Download the skeleton file THeaps.elm, and it as a starting point for this problem. Look for all occurrences of Debug.todo, 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 Nodes in the Tree):
type Heap a = Heap (Int, Tree a)You will implement all operations of the min-heap abstraction except for merge.
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) + 2To 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 << fooFor example:
> import THeaps exposing (..)
> pathTo 0
[] : List Dir
> pathTo 1
[Left] : List Dir
> pathTo 2
[Right] : List Dir
> pathTo 3
[Left,Left] : List Dir
> pathTo 10
[Left,Right,Right] : List Dir
> pathTo 58
[Right,Right,Left,Right,Right] : List DirFirst, implement the following Heap operations:
empty : Heap comparable
isEmpty : Heap comparble -> Bool
findMin : Heap comparable -> Maybe comparableNext, implement the insert operation:
insert : comparable -> Heap comparable -> Heap comparableYou may consider using the helper functions above, but you are free to implement insert however you wish.
Spoiler Alert: There are hints below.
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.
Download the skeleton file LHeaps.elm and use it as a starting point for this problem. Look for all occurrences of Debug.todo, which point out where you should implement your solutions.
Define
fromList : List comparable -> Heap comparablesuch 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
mergePairs hs takes, where n is the length of hs and m is the size of the largest heap in hs, andmakePass hs takes, where n is the length of hs and m is the size of the largest heap in hs.Download the skeleton files BHeaps.elm and ExplicitMin.elm and use them as a starting point for this problem. Look for all occurrences of Debug.todo, which point out where you should implement your solutions.
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.
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 files THeaps.elm (optional), 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:
% elm make Foo.elm
Success! Compiled 1 module.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 hw4
% cd hw4
% wget http://www.classes.cs.uchicago.edu/archive/2020/spring/22300-1/assignments/hw4/THeaps.elm
% wget http://www.classes.cs.uchicago.edu/archive/2020/spring/22300-1/assignments/hw4/LHeaps.elm
% wget http://www.classes.cs.uchicago.edu/archive/2020/spring/22300-1/assignments/hw4/BHeaps.elm
% wget http://www.classes.cs.uchicago.edu/archive/2020/spring/22300-1/assignments/hw4/ExplicitMin.elmIf 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 THeaps.elm # optional
% svn add LHeaps.elm
% svn add BHeaps.elm
% svn add ExplicitMin.elmMake sure you choose the same exact names for directories and files that you create. Once you are ready to submit:
% svn commit -m "hw4 submission"You can resubmit as many times as you wish, and we will grade the most recent versions submitted. Late days, if any, will be computed based on your submission times.
As a sanity check, you can visit the Web-based frontend for your repository to make sure that you have submitted your files as intended:
https://phoenixforge.cs.uchicago.edu/projects/USER-cs223-spr-20/repository
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 comparableOne 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.todo "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