# Problem 50

# Skip list PQ

**Due**: February 23

**Points**: 2

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.