我正在寻求实现一个优先级队列与一个增加的要求，一个查找/搜索功能，它会告诉一个项目是否在队列中的任何地方。所以这些函数将是：插入，删除和查找。具有查找功能的优先级队列 - 最快的实现
我不确定是否应该使用Heap或自平衡二叉搜索树。看起来PQ通常用堆实现，但我想知道在使用二叉搜索树时是否有优势，因为我也需要这个查找函数。
此外，平均而言，我会做更多的插入比删除。我也在考虑d-ary heap。基本上，每一秒都很重要。
谢谢！
IIRC在堆上搜索/查找是O(n)而树上是O(log(n))，其他标准PQ操作是相同的。
堆只是经验上更有效的一些常数因子，所以如果它是一个大排队树应该更好，如果它的小，你需要测试和配置文件。从理论上讲，理论上它们都更快，但如果这些常数因子很大，那么对于足够小的数据集可能完全不相关。
我低估了这个答案，因为它是错误的。堆和搜索树有不同的操作支持和不同的复杂性。在堆中的find-min是O（1），而在平衡搜索树中是'O（log n）'。插入一些堆是'O（1）'，在搜索树中是'O（log n）'。这不仅仅是理论。这些“O（log n）”与“O（1）”的复杂性可能会造成巨大的性能损失。 – Celelibi 2016-01-06 12:32:16
为什么你不能只使用优先级队列和设置？当你排队时，你将它添加到集合中。当您将其出列时，将其从集合中删除。这样一来，这套设备会告诉你是否有什么东西在队列中。
如果你的查找操作相对不频繁（而且你的堆很小），我只是做一个线性搜索。如果它比较频繁，或堆很大，可以考虑使用单独的数据结构或对象标志来跟踪堆成员资格（执行'查找'测试）。外部索引的喜悦是能够把你的对象放在尽可能多的容器中。
如果通过'查找'您确实是指'查找和修改'（我发现我经常需要从优先队列中删除与典型插入/删除分开的事情），下面是我使用的三种方法：
由于在一个相当小的工作集（500-1000）内插入/删除（100k/s连续）的速率很高，找到 - 删除的速率很低（比如1/s），我做了一个线性搜索该元素，然后以标准方式从树中删除它。
鉴于插入/删除分钟的高速率以及相当频繁的查找删除操作，我在间接查找它们后简单地将删除的对象标记为“无趣”。实际的空闲被推迟到对象正常出列为止。
给定一个小的std :: priority_queue（它没有插入/ del-min之外的访问方法）只有少数元素和很少的删除，我只是将整个队列复制到临时std :: vector并复制修改/期望的部分回到队列中。然后，我哭了自己睡觉。
“无趣”的旗帜可能是我的救命稻草。 – 2013-04-17 23:03:18
将您的数据存储在您测试过的最快的容器中，并使用bloom过滤器来测试容器中是否有东西。
我在之前的项目中使用散列表交配布隆过滤器，并在散列表上加速了400次，平均约为10k个项目。
布隆过滤器中有一些有趣的特性：
您不能从布隆过滤器中删除元素，因此一旦您弹出（），布隆过滤器将在此处显示该元素。最终，布隆过滤器将会_always_ show _anything_在那里。 – 2012-03-09 19:55:00
如果你需要一个以上的数据结构的好处，那么您可以在组成使用它们。例如，如果您需要优先级队列和二进制搜索树的好处，请对它们进行所需的操作。
如果是insert那么将这个元素插入到它们两个中。
如果是find那么您可以使用二叉搜索树找到该元素，如果找到该元素，则继续在优先级队列中找到它。
如果它是min那么先将它从优先级队列中删除，现在您知道它是哪个元素，那么您可以从二叉搜索树中将其删除。
如果它是del那么首先在二叉搜索树中找到它并将其删除，然后继续在优先级队列中找到它并将其从中删除。
假定二叉树的节点和优先级队列的节点是指向你的元素的指针。
Radix trees具有min-heap属性将提供您需要的属性。这实际上会给你的操作带来时间上的复杂性。例如，如果我们看一下this Haskell implementation，您提到的所有三个操作的时间复杂度为O（min（n，W））。其中n是元素的数量，而W是int（32或64）中的位数。
“平均来说，我会做更多的插入操作，而不是删除操作” - 这是你的意思吗？如果是这样的话，你最终会耗尽记忆，不是吗？ – paxdiablo 2010-10-20 02:42:57
优先队列用于路径寻找算法。当我达到目标时，我可以删除优先级队列的剩余部分，而不需要任何重新平衡。 – Harry 2010-10-20 02:53:25
@paxdiablo - 其他方式根本不可能...不是每个程序都是长时间运行的 – tobyodavies 2010-10-20 04:41:23