1

单调优先级队列是否有可能:

  1. O(1) 用于查找和删除具有最高优先级的项目,
  2. O(1) 用于插入项目,假设给定的优先级低于所有其他项目,
  3. O(log n) 用于在没有假设的情况下插入和删除项目?

我确实知道通过使用链表是否允许插入和删除是 O(n)。我也在考虑跳过列表。但是,在最坏的情况下,插入和删除项目是 O(n)。

不需要减少键。

4

1 回答 1

2

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

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

于 2016-03-12T16:26:54.553 回答