实现双端优先级队列的最佳方式是什么？
我想实现一个具有以下约束的双端优先级队列:
>
需要在固定大小的数组中实现。例如100个元素。如果在数组已满后需要添加新元素，则需要删除最旧的元素
需要最大和最小的O（1）
如有可能，插入O（1）
如果可能，去掉O(1)中的最小值
如果可能，清除O(1)中的空/初始化状态
O(1)中当前数组中元素的个数
我希望 O（1） 用于上述所有 5 个操作，但不可能在同一实现中对所有这些操作使用 O（1）。至少 3 个操作上的 O（1） 和另外 2 个操作上的 O（log（n）） 就足够了。
如果能为这种实现提供任何指示，将不胜感激。
共有3个答案
如果你绝对需要max和min为O(1 ),那么你可以做的是创建一个链表，其中你不断地跟踪min、max和size，然后将所有的节点链接到某种树结构，可能是一个堆。Min、max和size都是常数，因为查找任何节点都是在O(log n)中，所以insert和remove都是log n。清理将是微不足道的。
二进制堆将在< code>O(log n)中为您提供最少的插入和移除操作，在< code>O(1)中提供其他操作。
唯一棘手的部分是在数组已满后删除最旧的元素。为此，请保留另一个数组：
time[i] = at what position in the heap array is the element
added at time i + 100 * k.
每迭代100次，就增加< code>k。
然后，当数组第一次填满时，您删除< code>heap[ time[0] ]，当数组第二次填满时，您删除< code>heap[ time[1] ]，...，当它填满第100次时，您再次回绕并移除< code>heap[ time[0] ]等。当它第< code>k次填满时，您移除< code > heap[time[k % 100]](100是您的数组大小)。
确保在插入和删除元素时也更新time数组。
如果您知道任意元素的位置，则可以在O（log n）中删除任意元素：只需将其与堆数组中的最后一个元素交换，然后筛选您已交换的元素。
有许多专门的数据结构可以做到这一点。一个简单的数据结构是min-max堆，它是作为二进制堆实现的，其中层在“最小层”（每个节点小于或等于其后代）和“最大层”（每个节点大于或等于其后代）之间交替。最小值和最大值可以在时间 O（1） 中找到，并且，与在标准二进制堆中一样，排队和取消排队可以在时间 O（log n） 时间内完成。
您还可以使用间隔堆数据结构，这是任务的另一个专用优先级队列。
或者，您可以使用两个优先级队列 - 一个按升序存储元素，另一个按降序存储元素。每当插入值时，都可以将元素插入到两个优先级队列中，并让每个队列存储指向另一个的指针。然后，每当取消最小值或最大值的排队时，都可以从另一个堆中删除相应的元素。
作为另一种选择，您可以使用平衡二叉查找树来存储元素。然后可以在时间O（log n）中找到最小值和最大值（如果您缓存结果，则为O（1）），并且可以在时间O（log n）中完成插入和删除。如果您使用的是C，您可以为此使用std::map，然后使用start（）和rstart（）分别获取最小值和最大值。
希望这有帮助！
-
我看到的替换优先级队列比较器的公认答案是在新的比较类中重载操作符。 然而，我想为队列实现几个（10）不同的比较函数，并在运行时在main（）中创建pq时选择一个。我必须做10个不同的比较类还是有更简单的方法来做到这一点？
-
我目前正在尝试实现min heap PQ，但是我在实现的正确性方面遇到了一些问题，我似乎无法找出我做错了什么——它没有输出最低优先级，也没有对它们进行正确排序。 使用以下测试数据： 我得到以下结果： 我希望结果是按升序排列的——起初我认为这可能是因为交换了错误的孩子，但最后一个输出是最大的优先级，所以这没有意义。我花了几个小时试图研究堆优先级队列，但我找不到任何帮助。 以下是CMP要求的更好的代码
-
我正在编写一个涉及堆实现的代码，在我的bubbleUp方法中，在我的while循环行中，我似乎遇到了一个取消引用的错误。这可能是一个相当基本的问题，但解决这个问题的最佳方法是什么？我在实现removeHigh方法时也遇到了一些问题，该方法旨在从队列中移除最高的元素。
-
我正在尝试实现一个优先级队列，它的功能与普通的优先级队列有点不同。这里的想法是支持快速插入，但对最高优先级项目的访问较慢。在这种情况下，Insert方法将新项放在任何方便的地方；因此，remove和peek方法必须在整个队列中搜索最高优先级的项。 ////测试文件 我已经能够实现除remove和peek之外的所有方法，因为我无法获得实现这些方法的正确逻辑。我不知道如何搜索整个队列来找到最高优先级的
-
本文向大家介绍python实现最大优先队列，包括了python实现最大优先队列的使用技巧和注意事项，需要的朋友参考一下 本文实例为大家分享了python实现最大优先队列的具体代码，供大家参考，具体内容如下 说明：为了增强可复用性，设计了两个类，Heap类和PriorityQ类，其中PriorityQ类继承Heap类，从而达到基于最大堆实现最大优先队列。 测试结果： 以上就是本文的全部内容，希望对大
-
问题 怎样实现一个按优先级排序的队列？ 并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素 解决方案 下面的类利用 heapq 模块实现了一个简单的优先级队列： import heapq class PriorityQueue: def __init__(self): self._queue = [] self._index = 0