我想实现一个具有以下约束的双端优先级队列:
需要在固定大小的数组中实现..比如 100 个元素..如果数组满后需要添加新元素，则需要删除最旧的元素
需要 O(1) 中的最大值和最小值
如果可能，在 O(1) 中插入
如果可能，删除 O(1) 中的最小值
如果可能，在 O(1) 中清空/初始化状态
O(1) 中当前数组中元素的个数
我希望以上 5 个操作的复杂度为 O(1)，但不可能在同一个实现中对所有这些操作都使用 O(1)。至少 3 个操作的 O(1) 和其他 2 个操作的 O(log(n)) 应该足够了。
如果可以为此类实现提供任何指示，我们将不胜感激。
最佳答案
为此有许多专门的数据结构。一种简单的数据结构是最小-最大堆，它被实现为一个二叉堆，其中层在“最小层”(每个节点小于或等于其后代)和“最大层”(每个节点大于或等于它的后代。)最小值和最大值可以在时间 O(1) 中找到，并且，与在标准二叉堆中一样，入队和出队每次都可以在时间 O(log n) 内完成。
您还可以使用 interval heap data structure ，这是该任务的另一个专用优先级队列。
或者，您可以使用两个优先级队列 - 一个按升序存储元素，一个按降序存储元素。每当您插入一个值时，您就可以将元素插入到两个优先级队列中，并让每个队列都存储一个指向另一个的指针。然后，无论何时将 min 或 max 出队，都可以从另一个堆中删除相应的元素。
作为另一种选择，您可以使用平衡二叉搜索树来存储元素。然后可以在 O(log n) 时间内找到最小值和最大值(如果缓存结果则为 O(1))，并且可以在 O(log n) 时间内完成插入和删除。如果您使用的是 C++，您可以为此使用 std::map 然后使用 begin() 和 rbegin() 来获取分别是最小值和最大值。
希望这对您有所帮助!
关于algorithm - 实现双端优先级队列的最佳方式是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17556999/