Приоритетная очередь с O(1) delete-max, insert-min, find-min и O(log n) для вставки и удаления

Question

Возможно ли, чтобы очередь с монотонным приоритетом имела:

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

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

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

Answer 1

В амортизированном смысле красно-черные деревья обладают этим свойством. В худшем случае вы можете использовать одну из множества схем "пальчикового дерева", например , "Простое сбалансированное дерево поиска Флайшера с O(1) наихудшим временем обновления".

Я написал длинный обзор того, как эти вещи работают.