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.