我正在考虑实现一个带有附加要求的优先级队列,一个查找/搜索功能,它将判断一个项目是否在队列中的任何位置。所以函数将是:插入、删除和查找。
我不确定我应该使用堆还是自平衡二叉搜索树。看起来 PQ 通常是用堆实现的,但我想知道使用二叉搜索树是否有任何优势,因为我也需要那个 find 函数。
此外,平均而言,我会做更多的插入而不是删除。我也在考虑一个d-ary heap。基本上,每一秒都很重要。
谢谢!
我正在考虑实现一个带有附加要求的优先级队列,一个查找/搜索功能,它将判断一个项目是否在队列中的任何位置。所以函数将是:插入、删除和查找。
我不确定我应该使用堆还是自平衡二叉搜索树。看起来 PQ 通常是用堆实现的,但我想知道使用二叉搜索树是否有任何优势,因为我也需要那个 find 函数。
此外,平均而言,我会做更多的插入而不是删除。我也在考虑一个d-ary heap。基本上,每一秒都很重要。
谢谢!
为什么不能只使用优先队列和集合?当您将某些东西排入队列时,您将其添加到集合中。当您将其出列时,您将其从集合中移除。这样,集合会告诉你是否有东西在队列中。
如果您的查找操作相对不频繁(并且您的堆相当小),我只会进行线性搜索。如果比较频繁,或者堆很大,请考虑使用单独的数据结构或对象标志来跟踪堆成员资格(以进行“查找”测试)。外部索引的乐趣在于能够将您的对象放入任意数量的容器中。
如果“查找”您的真正意思是“查找和修改”(我发现我经常需要从优先级队列中删除内容,独立于典型的插入/删除),这里是我使用的三种方法:
鉴于在相当小的工作集(500-1000)上插入/删除分钟的高速率(连续 100k/s)和查找删除的低速率(例如 1/s),我对元素进行了线性搜索并然后以标准方式将其从树中删除。
鉴于插入/删除的高频率加上相当频繁的查找删除,我只是在间接找到删除的对象后将它们标记为“无趣”。实际的空闲被推迟到对象正常出队。
给定一个小的 std::priority_queue (除了 insert/del-min 之外没有访问方法),只有几个元素和相当少的删除,我只是将整个队列复制到一个临时 std::vector 并复制修改/期望部分回到队列中。然后我哭着睡着了。
如果您需要多个数据结构的好处,那么您可以在组合中使用它们。例如,如果您需要优先级队列和二叉搜索树的好处,那么对它们都执行您想要的操作。
如果是,insert
则将元素插入到它们两个中。
如果是,find
那么您可以使用二叉搜索树找到该元素,如果找到,则继续在优先级队列中找到它。
如果它min
首先从优先级队列中删除它,现在您知道它是哪个元素,那么您可以将它从二叉搜索树中删除。
如果是del
则首先在二叉搜索树中找到它并将其删除,然后继续在优先级队列中找到它并将其也从那里删除。
假设二叉树的节点和优先级队列的节点是指向您的元素的指针。
IIRC 在堆上搜索/查找是O(n)
在树上,而在树上是O(log(n))
,其他标准 PQ 操作是相同的。
堆只是通过一些常数因素在经验上更有效,所以如果它是一个大队列,一棵树应该更好,如果它很小,你需要测试和分析。理论上知道什么更快,但如果这些常数因素很大,它可能与足够小的数据集完全无关。
具有最小堆属性的基数树将提供您需要的属性。这实际上会给您的操作带来持续的时间复杂性。例如,如果我们看一下这个 Haskell 实现,你提到的所有三个操作都有时间复杂度O(min(n,W))。其中n是元素的数量,W是 int 中的位数(32 或 64)。
请检查此代码。我编写了这个程序,这是一个具有您需要的功能的优先级队列。
1. Insert
2. Find
3. Delete
4. Show
你可以试试。它运行良好。在这里,我将升序最小数字添加到最大数字。
我使用优先级队列默认功能通过开关盒来做到这一点。
queue.push()
queue.pop()
queue.top()
queue.size()
C++ 代码:
#include<bits/stdc++.h>
#include <queue>
using namespace std;
void show_queue(
priority_queue<int, vector<int>, greater<int> > data)
{
priority_queue<int, vector<int>,greater<int> > myq = data;
while (!myq.empty()) {
cout << '\t' << myq.top();
myq.pop();
}
cout << '\n';
}
int main()
{
priority_queue<int, vector<int>,greater<int> > myp_queue;
while(1)
{
int choice;
cout<<"\nwhat do you want to do?"<<endl;
cout<<"1. Insert \n2. Find \n3. Delete \n4. Show Queue \n\nchoice your option from above: ";
cin>>choice;
switch(choice)
{
case 1:
int n;
cout<<"Enter the value: " ;
cin>>n;// Option 2 => Insert
myp_queue.push(n);
break;
case 2:
if(!myp_queue.empty()){
cout<<"\n"<<myp_queue.top()<<" is the minimum number"<<endl; // Find the minimum number.
}else{
cout<<"\nEmpty Priority Queue"<<endl;
}
break;
case 3:
if(!myp_queue.empty()){
myp_queue.pop(); //Delete the minimum number from the queue
cout<<"\nSuccessfully Deleted"<<endl;
}else{
cout<<"\nThere is no element to delete"<<endl;
}
break;
case 4:
if(!myp_queue.empty()){
show_queue(myp_queue); // Show full queue
}else{
cout<<"\nEmpty Priority Queue"<<endl;
}
break;
default:
cout<<"\nYou are terminated!!! \nYou entered wrong input.\n"<<endl;
}
}
return 0;
}
将您的数据存储在您测试过的最快的容器中,并使用布隆过滤器来测试容器中是否有东西。
我在之前的项目中将布隆过滤器与哈希表结合使用,它在哈希表上的处理速度提高了 400 倍,平均大约有 10k 个项目。
布隆过滤器有一些有趣的特性: