在O(1)时间内支持Min,Max操作的队列的正确数据结构是什么？

Question

支持Enque,Dequeue,Peak,Min和Max操作的队列的正确数据结构是什么,并在O(1)时间内执行所有这些操作.

最明显的数据结构是链表,但Min,Max操作将是O(n).Priority Queue是另一个完美的选择,但Enqueue,Dequeue应该以Queue的正常方式工作.(FIFO)

想到的另一个选项是Heap,但是我无法弄清楚如何使用Heaps设置具有Min,Max操作的队列.

任何帮助深表感谢.

Answer 1

任何可以检索Min或Max在O(1)时间内的数据结构都需要在每个上花费至少O(log n)Insert并Remove以部分排序的顺序维护元素.实现此目的的数据结构称为优先级队列.

基本优先级队列支持Insert,Max以及RemoveMax.有许多方法可以构建它们,但二进制堆最有效.

支持所有的Insert,Min,RemoveMin,Max,并RemoveMax用一个单一的优先级队列更为复杂.本文描述了一种使用二进制堆改编的单一数据结构的方法:

Atkinson,Michael D.,et al." Min-max堆和广义优先级队列. "ACM 29.10(1986)的通信:996-1000.

它速度快,内存效率高,但需要很多小心才能正确实现.

Answer 2

如果min()和max()实际上改变了结构,则无法设计您寻找的数据结构.如果min()和max()与peek()类似,并提供只读访问权限,那么你应该按照这个问题中的步骤,添加另一个deque,类似于用于max()的min()操作的deque( )操作.本答案的其余部分假设min()和max()实际上删除了相应的元素.

由于您需要enqueue()和dequeue(),因此必须按到达顺序(FIFO)添加和删除元素.一个简单的双端队列(链接或使用圆形向量)将在O(1)中提供此功能.

但是要添加的元素可能会改变当前的min()和max(); 但是,删除后,应恢复旧的min()和max()值...除非它们在过渡期间被删除.此限制会强制您以某种方式对元素进行排序.任何排序结构(最小堆,最大堆,平衡二叉树,......)都需要至少O(log n)才能找到新到达的位置.

最好的办法是将平衡二叉树(min()和max())与双向链表配对.您的树节点将存储一组指向列表节点的指针,按照您在min()和max()中使用的任何键进行排序.在Java中:

// N your node class; can return K, comparable, used for min() and max() 
LinkedList<N> list;           // sorted by arrival
TreeMap<K,HashMap<N>> tree;   // sorted by K

• 在enque()上,您将添加一个新节点到其末尾list,并通过其键将该节点添加到HashMap其节点中tree.O(log n).
• 在dequeue()上,您将从list树的节点中的HashMap 开始删除该节点.O(log n).
• 在min()上,你会在树中寻找第一个元素.O(1).如果你需要删除它,你有指向链表的指针,所以那边是O(1); 但是如果它是具有特定K的最后一个元素,则O(log n)重新平衡树.
• 在max()上,同样的逻辑适用; 除了你要寻找树中的最后一个元素.所以O(log n).
• 在peek()上,查看但不提取队列中的第一个元素将是O(1).

如果您知道所有键都是唯一的,则可以简化此操作(通过删除HashMap).但是,这不会影响渐近成本:它们都会保持不变.

实际上,O(log n)和O(1)之间的差异非常小,以至于C++的STL中的默认映射实现是基于O(log n)的(树而不是Hash).