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.

The opposite of a treap

Due: March 8
Points: 3

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?