具有查找功能的优先级队列-最快的实现 [英] Priority Queue with a find function - Fastest Implementation

问题描述

我正在考虑实现具有附加要求的优先级队列，即查找/搜索功能，该功能将告知项目是否在队列中的任何位置.这样的功能将是:插入，删除和查找.

我不确定我应该使用堆还是自平衡二进制搜索树.看来PQ通常是用Heap实现的，但是我想知道使用二进制搜索树是否有任何优势，因为我也需要该find函数.

此外，平均而言，插入操作要多于删除操作.我还在考虑 d-ary堆.基本上，每一秒都很重要.

谢谢！

解决方案

如果您的find操作相对较少(并且您的堆很小)，我将进行线性搜索.如果相对频繁或堆很大，请考虑使用单独的数据结构或对象标志跟踪堆成员身份(进行查找"测试).外部索引的乐趣在于可以将对象放入任意数量的容器中.

如果查找"实际上是查找并修改"(我发现我经常需要独立于典型的insert/del-min来从优先级队列中删除内容)，那么我使用了以下三种方法:

鉴于在相当小的工作集(500-1000)上插入/删除时间(连续100k/s)的速率很高，而查找/删除的速率(例如1/s)很低，我进行了线性搜索元素，然后以标准方式将其从树中删除.

考虑到较高的插入/删除时间以及相当频繁的查找-删除，我在间接找到被删除的对象之后将其标记为无趣".实际的空闲时间会推迟到该对象正常出队之前.

给出一个只有几个元素并且很少删除的小std :: priority_queue(在insert/del-min之外没有访问方法)，我只是将整个队列复制到一个临时std :: vector并复制了修改过的/所需的零件返回队列.然后我哭了睡.

I am looking at implementing a priority queue with an added requirement, a find/search function which will tell whether an item is anywhere within the queue. So the functions will be: insert, del-min and find.

I am unsure whether I should use a Heap or a Self-balancing binary search tree. It appears PQs are usually implemented with a Heap, but I am wondering if there is any advantage in using a binary search tree since I also need that find function.

Furthermore, on average I'll be doing more inserts than deletes. I am also considering a d-ary heap. Basically, every second counts.

Thanks!

解决方案

If your find operation is relatively infrequent (and your heap fairly small), I'd just do a linear search. If it is relatively frequent, or the heap is enormous, consider tracking heap membership (to do your 'find' test) with a separate data structure or an object flag. The joy of external indexing is being able to put your object in as many containers as you like.

If by 'find' you really mean 'find and modify' (I find I often need to delete things from priority queues independently of the typical insert/del-min), here are three approaches I've used:

Given a high rate of insert/del-min (100k/s continuous) and a low rate of find-delete (say 1/s) over a fairly small working set (500-1000) I did a linear search for the element and then deleted it from the tree in the standard way.

Given a high rate of insert/del-min plus fairly frequent find-deletes I simply marked the deleted objects as "uninteresting" after finding them indirectly. The actual free was deferred until the object was dequeued as normal.

Given a small std::priority_queue (which has no access methods outside of insert/del-min) of only a few elements and fairly infrequent deletions, I just copied the entire queue to a temporary std::vector and copied the modified/desired part back into the queue. Then I cried myself to sleep.

这篇关于具有查找功能的优先级队列-最快的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！