Problem 37

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:

**Insert**: Insert a new item with the given priority into the PQ.**Delete-min**: Remove the item with the smallest priority from the PQ.

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.