Brown Heaps
1 The Assignment
2 Implementing Operations
3 Template Files
4 Handing In

Brown Heaps

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).

1 The Assignment

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 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.

data BHeap:

  | mt

  | node(value :: Number, left :: BHeap, right :: BHeap)


2 Implementing Operations

When implementing operations for this assignment, you will use the above BHeap data definition, subject to the following additional conditions:
  • 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.

You will need to implement three operations on Brown heaps
  • 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 \rightarrow \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.

3 Template Files

We will, as usual, be using Captain Teach:

The templates are here:

Initial Tests

Implementation Code

Final Tests

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.

4 Handing In

Remember that this assignment requires you to hand in sweeps.

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!—and please do attribute the ones you copied to to peer-reviewing, even though you won’t be able to name the author).