algorithm - 具有 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

在摊销意义上，红黑树具有此属性。在最坏的情况下，您可以使用许多手指树设计中的一种，例如Fleischer 的“A Simple Balanced Search Tree with O(1) Worst Case Update Time”。

我写了一篇关于这些东西如何工作的长篇概述。