Priority queue with O(1) delete-max, insert-min, and find-min and O(log n) insertion and deletion

1
votes

Is it possible for monotonic priority queue to have :

  1. O(1) for finding and delete item with highest priority,
  2. O(1) for inserting item assuming the priority given is lower than every other item,
  3. O(log n) for inserting and deleting item without assumption?

I do know if the insertion and deletion is allowed to be O(n), by using linked list. I was also thinking of skip list. However, in worst case, inserting and deleting item is O(n).

Decrease-key is not required.

1
algorithmdata-structuresfinger-tree

1 Answers

2
votes

In an amortized sense, red-black trees have this property. In the worst-case, you can use one of many finger-tree designs, like Fleischer's "A Simple Balanced Search Tree with O(1) Worst Case Update Time."

I wrote a long overview of how these things work.