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,
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 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
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
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:
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
Linking is a pervasive helper for other binomial tree/heap operations.
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
Binomial trees and heaps have an analogy with binary numbers. A tree of rank r has 2
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
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 [ 12 , 6 8 , some rank-10 tree, etc.] same rank, link, recurse = insertTree 12 17 [ 6 8 , some rank-10 tree, etc.] same rank, link, recurse = insertTree 6 12 17 8 [some rank-10 tree, etc.] different ranks, done 3 = [ 6 12 17 8 , some rank-10 tree, etc.] 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
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
• Either or both input heaps is/are empty.
• The input heaps are h1 = t1 : g1 and h2 = t2 : g2, and the ranks of t1 and t2 are different.
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
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.
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx