Skip list PQDue: February 23
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.