如何实现双端优先队列的最佳方法？

Question

如何实现双端优先队列的最佳方法？

algorithmdata-structuresbig-opriority-queueheapsort

4

我想实现一个双端优先队列，具有以下约束条件：

必须在固定大小的数组中实现。比如说100个元素。如果在数组已满后需要添加新元素，则需要删除最旧的元素。
最大值和最小值需要在O(1)内找到。
如果可能，在O(1)内插入元素。
如果可能，在O(1)内删除最小值。
如果可能，在O(1)内清空/初始化状态。
在任何时刻数组中的元素数量计数应该在O(1)内完成。

我希望上述5个操作都可以在O(1)内完成，但是在同一实现中不可能同时实现所有操作的O(1)效率。至少在3个操作上达到O(1)，并在另外2个操作上达到O(log(n))的效率就足够了。

如果您有指针可以提供这样的实现，将不胜感激。

- Medicine

你尝试过什么吗？至少在O(1)时间复杂度下清空/初始化状态对于了解基本数据结构的人来说并不是那么简单 :( - Fallen

@Fallen，也要将计数器加1..只需跟踪它..我只是在明确操作和时间复杂度：)，这样建议特定实现的人就会对期望有清晰的了解。 - Medicine

嗯，你不能同时在常数时间或摊销常数时间内实现插入和提取最小/最大值，因为这将意味着一个线性时间的排序算法。这一切都是基于假设你的键不是整数或类似的，而是具有比较运算符的黑盒子。 - user395760

4个回答

2

一个二叉堆可以在O(log n)的时间内插入和删除最小值，而其他操作则只需O(1)的时间。

唯一棘手的部分是当数组已满时如何删除最旧的元素。为此，请保留另一个数组：

time[i] = at what position in the heap array is the element 
          added at time i + 100 * k.

每100次迭代，您会增加变量k的值。
然后，当数组第一次填满时，您会删除heap[time[0]]；当它第二次填满时，您会删除heap[time[1]]；...；当它第100次填满时，您会循环并再次删除heap[time[0]]等等。当它第k次填满时，您会删除heap[time[k%100]]（100是数组大小）。请确保在插入和删除元素时也更新time数组。
如果您知道要删除元素的位置，则可以在O(log n)时间内对任意元素进行删除：只需将其与堆数组中的最后一个元素交换位置，然后将交换进来的元素下沉即可。

- IVlad

我们怎么能在O(1)的时间复杂度内找到一个二叉堆中的最小值和最大值呢？我认为我们只能在O(1)的时间复杂度内找到其中一个，具体取决于它是最小堆还是最大堆。 - Medicine

@Medicine - 保持两个堆，或者参考templatetypedef的回答。 - IVlad

好的，要从最小堆中删除最小值，可以在O(log(n))时间内完成。那么如果要从最大堆中删除相同的元素，需要额外的努力吗？ - Medicine

@Medicine - 相同的，O(log n)。2*O(log n) = O(log n)。你可以通过保持类似于“时间”的数组来查看一个元素在另一个中的位置。然而，如果使用最小-最大堆，则可能需要更少的工作。 - IVlad

我在考虑使用minmax堆，但需要一个参考实现。 - Medicine

0

如果您绝对需要max和min为O(1)，那么您可以创建一个链表，在其中不断跟踪最小值、最大值和大小，然后将所有节点链接到某种树结构中，可能是堆。最小值、最大值和大小都将是常数，由于查找任何节点都是O(log n)，因此插入和删除每个节点都是log n。清除将是微不足道的。

- Eric Kim

-1

如果您的队列是固定大小的，则O-notation毫无意义。任何O(log n)甚至O(n)操作本质上都是O(1)，因为n是固定的，所以您真正想要的是针对给定数据集快速的算法。可能两个并行的传统堆优先队列就足够了（一个用于高优先级，一个用于低优先级）。

如果您更了解您拥有的数据类型，您可能能够创建一些更特殊用途的东西。

- Lee Daniel Crocker

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

有许多专用的数据结构可以实现此目的。一个简单的数据结构是最小-最大堆，它是二叉堆的一种，层次结构在“最小层”（每个节点小于或等于其后代）和“最大层”（每个节点大于或等于其后代）之间交替。最小值和最大值可以在O(1)时间内找到，类似于标准二叉堆，每个元素在入队和出队时所需的时间都是O(log n)。

您还可以使用区间堆数据结构，这是另一种专用的优先队列。

另外，您也可以使用两个优先队列，一个按升序存储元素，另一个按降序存储元素。每当插入一个值时，您可以将元素插入到两个优先队列中，并让每个队列存储对另一个队列的指针。然后，每当您出队最小值或最大值时，可以从另一个堆中删除相应的元素。

作为另一个选择，您可以使用平衡的二叉搜索树来存储元素。然后最小值和最大值可以在O(log n)（如果缓存结果，则为O(1)）的时间内找到，并且插入和删除可以在O(log n)的时间内完成。如果您使用C ++，则可以直接使用std :: map ，然后使用begin()和rbegin()分别获取最小和最大值。希望这有所帮助！