This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

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.