CSCC24 2020 Summer – Assignment 1
Due: Monday, June 22, midnight
This assignment is worth 10% of the course grade.
In this assignment, you will work in Haskell with algebraic data types and implementing interesting recursive functions.
As usual, you should also aim for reasonably efficient algorithms and reasonably organized, comprehensible code.
Binomial Heap
A binomial heap is a way to implement a mergeable priority queue. It consists of a list of binomial trees with conditions. So let’s begin with binomial trees.
Binomial Tree
Binomial trees are defined inductively:
• A binomial tree of rank 0 is one single node. (So it is the root node and it has 0 children.)
• A binomial tree of rank r + 1 (root has r + 1 children) is built by taking two binomial trees, both of rank r, and “linking” them—make one of them the first, leftmost child subtree of the other.
Equivalnetly: A binomial tree of rank r (natural number) has a root node with r children; the ranks of the children, in order, are r − 1, r − 2, …, down to 0.
To help implement priority queues, each node stores a priority, and there is a “heap order” requirement: comparing a parent node and a child node, parent’s priority ≤ child’s priority. (We are doing min priority queues in this assignment; we also omit storing jobs.)
Here are a few example pictures (priorities shown inside circles): rank 0 rank 1 rank 2 rank 3
17126 6 17 12 8 7 12 8
17 7 11 17 10
Note that, e.g., in the rank 2 example, the first child subtree is itself of rank 1; indeed the rank 2 example can come from:
1
link 12 6 = 6 178 128
17
Note that when linking, use root priorities to determine who becomes the new parent, who becomes the new child. In this example, 6 ≤ 12 settles it.
We use this Haskell data type to represent a binomial tree:
data BinomialTree a = Node Int a [BinomialTree a] — Fields: rank, priority, list of child subtrees
It is polymorphic in the actual type of priorities. The rank 2 example is represented as:
Node 2 6 [Node 1 12 [Node 0 17 []] , Node 0 8 []]
Question 1: link (2 marks)
Implement linking of two trees:
link :: Ord a => BinomialTree a -> BinomialTree a -> BinomialTree a
You may assume that the two trees have the same rank. Remember to use root priorities to decide who becomes the new parent (tie-breaking is up to you). And remember to calculate the new rank.
Linking is a pervasive helper for other binomial tree/heap operations.
Binomial Heap
A binomial heap is a list of binomial trees, [BinomialTree a], in order of strictly increasing ranks. (Be careful, this is the opposite of children order inside a tree.) (An empty heap is represented by an empty list.) Example:
[14,3, 6] 95 7128
16
7 11 17 10
2
Binomial trees and heaps have an analogy with binary numbers. A tree of rank r has 2r nodes. If a heap has n nodes (total over list of trees), then n in binary notation corresponds to which ranks are present in the list of trees. For example if n = 11012 (the example above), then the list has a tree of rank 0, a tree of rank 2, a tree of rank 3, and nothing else. Some heap operations are likewise analogous to incrementing and adding binary numbers.
Question 2: findMin (2 marks)
Implement finding the lowest priority in a heap:
findMin :: Ord a => [BinomialTree a] -> Maybe a
Note that this just needs scanning the list for the minimum root priority.
Question 3: insertTree (3 marks)
If we have the following helper operation, then inserting into a heap will be easy. The helper is called:
insertTree :: Ord a =>
BinomialTree a -> [BinomialTree a] -> [BinomialTree a]
It inserts a tree t into a heap h to produce a new heap. You may assume that, if h = t2 : ts, then t’s rank ≤ t2’s rank.
Recall that a heap, especially the new heap, must have ranks in strictly increasing order; you must not have two trees of the same rank.
If t’s rank < t2’s rank, that’s easy. But if they are equal, you’ve got work to do—you cannot just enter them both into the output list. Solution: Use link to combine them, then your new job is inserting the combined tree into the smaller heap ts, i.e., recursion. Example:
insertTree 17
= insertTree 12 17
[12, 6 , some rank-10 tree, etc.] 8
[6, some rank-10 tree, etc.] 8
same rank, link, recurse
same rank, link, recurse
different ranks, done
= insertTree
6 12 8
17
[some rank-10 tree, etc.]
3
= [ 6 , some rank-10 tree, etc.] 12 8
17
Note that using insertTree, inserting a priority into a heap is easy:
insert :: Ord a => a -> [BinomialTree a] -> [BinomialTree a] insert p heap = insertTree (Node 0 p []) heap
Question 4: Merge (3 marks)
Binomial heaps are mergeable heaps, i.e., unioning two heaps can be done efficiently. Implement merging:
merge :: Ord a =>
[BinomialTree a] -> [BinomialTree a] -> [BinomialTree a]
Recall that the two input heaps are each ordered by strictly increasing ranks, and the output heap also needs to be; you must not have two trees of the same rank. It is pretty obvious what to do if:
• Either or both input heaps is/are empty.
• Theinputheapsareh1 =t1 :g1 andh2 =t2 :g2,andtheranksoft1 andt2 aredifferent. The hard part is when t1 and t2 have the same rank—you cannot just enter them both into the
output list. Solution/hint:
1. Use recursion to merge g1 and g2, call it g3. Least worrisome part.
2. t1 and t2 have the same rank. Which helper function above combines them? Call the result t3.
3. You now have a tree t3 to be inserted into a heap g3. Which helper function above can do this for you? (You can prove that its precondition is met, but it’s true.)
(We won’t do extracMin in this assignment, but it would use merge.) End of questions.
4