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

Brown heaps

A heap is a data structure that holds comparable values and supports the following operations:

• insert : (Any$ BHeap$ → BHeap$)
  Takes an element elt of type Any$ and a heap with elements of type Any$ and returns a heap of Any$ containing all elements of h and elt.

• get-min : (BHeap$ → Any$)
  Takes a non-empty heap and returns its minimum value

• remove-min : (BHeap$ → BHeap$)
  Takes a non-empty heap of $Any h and returns a heap of Any$ containing all the elements of h except (get-min h).

For simplicity, in this assignment you should use heaps of numbers. Also, we will only be working with Brown Heaps (defined below), so all of your functions need only work with Brown Heaps, not any arbitrary heap.

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 structures to represent Brown heaps:

(define-struct: BhNode ([value : Any$] [left : BHeap$] [right : BHeap$]))
where value is an Any$ and left and right are BHeap$s.

(define-struct: MtHeap ())
to represent an empty Brown heap.

(define BHeap$ (or: BhNode$ MtHeap$))
where a BHeap$ is either:

• an MtHeap$, or
• a BhNode$, where
  • left and right are BHeap$s
  • 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.

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

Part 2

Analyze the time complexity of your implementations of the heap operations.

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 Racket code with your implementation of Brown heaps.

• A file, analysis.[txt,pdf,doc] with your answers for Part 2.
  As always, these files must be in plain text, pdf, or, if you really must, Word format. If you use Word, we will accept only Word 2003 (.doc) files. If you are using Word 2007, you should export to a pdf. We will not accept Word 2007 (.docx) files because we cannot read them.