Data Structures and Algorithms

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.

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.

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.

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.

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.