• Welcome
• README
• Assignments
• Readings
• Software
• Contact
• Credits

Brown heaps

A heap is a data structure that holds comparable values and supports insertion, retrieval of a minimum value, and removal of said minimum. We will define our heap with the following data type and associated procedures:

(define-type BHeap
  [mt]
  [node (value : number) (left : BHeap) (right : BHeap)])

Operations:

• (insert [elt : number] [heap : BHeap]) : BHeap
  Takes an element elt of type number and a heap with elements of type number and returns a heap of number containing all elements of heap and elt.

• (get-min [heap : BHeap]) : number
  Takes a non-empty heap and returns its minimum value

• (remove-min [heap : BHeap]) : BHeap
  Takes a non-empty heap of number, and returns a heap of number containing all the elements of heap except (get-min heap).

For simplicity, in this assignment you will only use heaps of numbers, but it should be easy to generalize for other types (for which comparison is defined). Also, your operations only need to work on heaps that match the invariants of Brown Heaps as defined below.

Heaps are most commonly represented as binary trees. Unlike binary search trees, though, heaps impose no ordering constraint on the elements in the left and right children of a node. Instead, heaps maintain the invariant that the value at each node is less than the values of either of its children. Thus the minimum element in a heap is always 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.

Part 1

Implement the three heap operations listed above for Brown heaps.

Use the following type to represent Brown heaps:

(define-type BHeap
  [mt]
  [node (value : number) (left : BHeap) (right : BHeap)])

Under these conditions:

• the number of nodes in left is the same or one greater than the number of nodes in right, and
• value is a number smaller than any value in left or right

All three operations 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. You can assume that there will be no duplicate values in a Brown Heap, and you will not be asked to insert an element already in it.

For testing purposes, we need you to use the function names and data definition above exactly as written.

Part 2

We would also like you to test your code using an oracle, just like the one you implemented in Sortacle and Oracle. We would like you to explain your testing strategy in your written analysis file.

Part 3

Analyze the time complexity of your implementations of the heap operations. Which operation is more costly: insert, or remove-min? Is this always the case?

Note: It is important to make sure your analysis correctly describes your implementation. You will receive full credit on this section only for an accurate analysis of your code, even if your code is suboptimal.

What to turn in:

• A Racket file, brown-heaps.rkt, containing plai-typed code with your implementation of Brown Heaps, along with an oracle that tests each facet of your code.

• A file, analysis.pdf with your answers for Part 3 and a description of your oracle's testing strategy.
  

Your analysis must be in a pdf file on Letter-sized paper. Mathematical content must be formatted appropriately. Please, no Arial.