# Haskell代写 | CSCC24 2020 Summer – Assignment 1

这个作业是用Haskell完成树相关的数据结构操作

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

17 12

17

6

12

17

8

6

7

7

10

11

12

17

8

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

17

6

8

= 6

12

17

8

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

9

16

5

, 6

7

7

10

11

12

17

8

]

2

Binomial trees and heaps have an analogy with binary numbers. A tree of rank r has 2

r 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 [ 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

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.

• 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

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