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.
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.
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 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 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.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.
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.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 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.htmlOne 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.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