This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
Recall from data structures that a priority queue has the following operations:
By far the most popular implementation of a priority queue is the heap, which takes \(\Theta(\log n)\) time for both insert and delete-min.
Show how a skip list could be used to implement the priority queue ADT. Explain how each operation would work, and tell me what the expected running time of each one would be.