очередь приоритета с O (1) Опустить-макс, вставки-мин, и найти-мин и O (журнал N) вставка и удаление

Question

Возможно ли очередь монотонной приоритет иметь:

1. O (1) для поиска и удаления элемента с наивысшим приоритетом,
2. O (1) для вставки элемента, если данный приоритет ниже, чем каждый другой элемент,
3. O (log n) для вставки и удаления элемента без предположения?

Я знаю, если вставка и удаление разрешено быть O (n), используя связанный список. Я тоже думал о списке пропусков. Однако в худшем случае вставка и удаление элемента - O (n).

Ключ уменьшения не требуется.

Answer 1

В амортизированном смысле, красно-черные деревья обладают этим свойством. В худшем случае, вы можете использовать один из многих конструкций пальцев дерева, как Fleischer's "A Simple Balanced Search Tree with O(1) Worst Case Update Time."

I wrote a long overview of how these things work.