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.

Skip list PQ

Due: February 8
Points: 3

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.