单调优先级队列是否有可能:
- O(1) 用于查找和删除具有最高优先级的项目,
- O(1) 用于插入项目,假设给定的优先级低于所有其他项目,
- O(log n) 用于在没有假设的情况下插入和删除项目?
我确实知道通过使用链表是否允许插入和删除是 O(n)。我也在考虑跳过列表。但是,在最坏的情况下,插入和删除项目是 O(n)。
不需要减少键。
单调优先级队列是否有可能:
我确实知道通过使用链表是否允许插入和删除是 O(n)。我也在考虑跳过列表。但是,在最坏的情况下,插入和删除项目是 O(n)。
不需要减少键。
在摊销意义上,红黑树具有此属性。在最坏的情况下,您可以使用许多手指树设计中的一种,例如Fleischer 的“A Simple Balanced Search Tree with O(1) Worst Case Update Time”。