A heap is a tree-based data structure that holds comparable values and focuses on the rapid access of smallest or largest values. For simplicity you will only use heaps of numbers in this assignment, but it should be easy to generalize for other types (for which comparison is defined).
Unlike search trees, heaps impose no ordering constraint on the elements in the children: e.g., they do not require that all values in the left child ben be no bigger than all values in the right child of a node. Instead, heaps maintain the invariant that the value at each node is less than (or equal to) the values of its children. Thus, the minimum element in the heap is always its root.These are known as min heaps. Naturally, it is also possible to have max heaps, where the largest element in a heap is at its root.
One way to optimize the worst-case time complexity of the heap operations is to keep the heap balanced. A tree is balanced if the depths of any two leaves differ by at most one. In order to maintain balance in our heap implementation, we will impose a stronger condition: at each node, the number of nodes in the left subheap of a node must be the same or one greater than the number of nodes in the right subheap. We will call heaps with this invariant Brown heaps, defined below.
In what follows, assume there will be no duplicate elements.
| node(value :: Number, left :: BHeap, right :: BHeap)
The number of nodes in left is the same or one greater than the number of nodes in right
value is a number smaller than any value in left or right.
insert :: (Number, BHeap -> BHeap)
insert consumes a Number and a Brown heap and produces a Brown heap consisting of all the elements of the given BHeap in addition to the given Number.
get-min :: (BHeap%(is-node) -> Number)
get-min consumes a non-empty Brown heap and produces the minimum value in that heap.
remove-min :: (BHeap%(is-node) -> BHeap)
remove-min consumes a non-empty Brown heap and returns a new Brown heap consisting of all the elements of the given Brown Heap except the element returned by get-min.
All operations in this assignment can be performed in \(O([s -> \log s])\) time or better, where \(s\) is the number of elements in the heap. We will be grading on efficiency. Once again, you can assume that there will be no duplicate values in a Brown heap; you will therefore not be asked to insert an element already in a heap. You will need to turn in an analysis stating what efficiency you obtained, and justifying it.
We will, as usual, be using Captain Teach:
The templates are here:
Note: Implementation-dependent testing should be in the implementation file. The final tests file should contain your tests for the three procedures we had you implement.
Keep in mind that the output of insert and remove-min may be implementation-dependent! Think carefully about how you can test all three procedures without directly checking the output of insert or remove-min.
You will need to also determine the run-time complexity of your implementation of insert, get-min, and remove-min.
As with previous assignments, you will submit an initial test sweep. This is due 11:59 PM, Tuesday, November 4th.
To submit your implementation, return to the Captain Teach assignments page:
and click “Next Step” again. This time, save and then upload a zip file of
both brown-heaps-tests.arr and brown-heaps-code.arr. You can include as many
tests as you want (beyond 10) for this final submission, and you can include
tests you saw while reviewing (but copy with care!—
After you submit your implementation, you’ll have one further step to complete.
We want you to answer a quick two-question survey about what (if any) impact
the peer review process had on your final submission. The interface will look
similar to the review interface, and once you submit your answers to the two
questions there, you’re done. Again, this feedback will have no effect on your