c++ - 如何获得队列的最小值和最大值？

Question

你能设计一个数据结构，就像一个包含'enqueue'、'dequeue'、'minimum'和'maximum'的队列吗？我知道一种使用 2 个堆栈创建队列以分别找到最小值和最大值的方法，但是我怎样才能同时获得两者？

谢谢

Answer 1

使用标准容器，像 a 这样的完全有序的数据结构std::set将提供对两个极值的访问，例如使用*s.begin()and *s.rbegin()。如果您有多个具有相同优先级的对象，您可能希望以任意方式打破关系，或者使用 astd::multiset代替。

大多数实现可能会使用某种形式的红黑树来实现这样的集合。由于数据结构将始终保持排序，渐近性能可能比常规单端基于堆的优先级队列给您的性能更差，但对于许多应用程序来说，差异并不重要，因此实现的工作量应避免使用自定义数据结构。

Answer 2

使用优先队列！

C++ STL

#include<queue>

通常，优先级队列是由 Binary-Heap 实现的。但它不能同时保持最大值和最小值。@_@

也许平衡搜索树，例如 AVL、Splay 或红黑树应该是更好的选择。

Answer 3

通常使用某种堆结构来实现优先级队列。有一种称为min-max 堆的变体，它允许对最大和最小元素进行恒定时间访问。已经有一个问题要求 C++ 实现这种最小-最大堆。它的答案也应该对你有用。

Paul Dixon的这篇评论首先提到了 min-max heaps，而Chris Mansley的这篇评论指出了 Stack Overflow 上的实现问题。

Answer 4

数据结构是一种众所周知的结构，称为优先级队列。队列中的每个元素都有一个关联的优先级，并且队列保持从高到低的排序顺序。

队列中的每个元素都必须携带一个优先级，并且代码必须维护订单合约。

一些 STL 包含优先级队列实现，但现在我看它，我不确定整个队列是否保持优先级顺序。