COMP2123 Assignment 3
March 2019
1 Problem 1
Overview and strategy: We need an algorithm to satisfy Heap-order property for the priorities
and binary search property for the keys. Heap-order property is that for each node n other than the
root, the key of that node is greater than or equal to the key of its parent. We don’t care about
completeness of our tree so we don’t have to fill up the external level strictly from left to right.
We notice that, in order to guarantee the heap-order of the priorities in the tree, we need to first sort
the given collection of priority-value pairs by priority. This will ensure that, when placing nodes into
the tree, a pair with the lowest priority will fill the root, followed by the next-lowest-priority pair and
so on. All we have to do next is to construct a binary tree using the values of the priority-value pairs.
Algorithm: For a two-dimensional list holding a priority and a value in each ”entry”, return null if
the list is empty, otherwise
1. Sort the entries by priority using selection-sort algorithm.
2. Construct a binary search tree as follows [used in assignment 3]:
