Problem 53

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

A treap inserts items with given keys into a dictionary structure, by using randomly-chosen priorities that will determine the actual arrangement. In this way, a treap performs similarly to AVL or 2-3 trees, except that it's a bit simpler to implement due to the randomization.

Consider the opposite of a treap, a paert: A paert is a randomized *priority queue* that inserts item with the given priorities into a priority queue structure, by randomly choosing a *key* for each inserted item and using that to determine the actual arrangement.

So a paert will look exactly like a treap, except that in a paert it's the priorities which come from the actual data, and the keys that are chosen randomly, rather than the other way around.

Two questions:

- Does a paert have similar expected-case performance to a heap?
- Is there any reason you can think of to use a paert instead of a heap?