具有查找功能的优先级队列 - 最快的实现

Question

我正在考虑实现一个带有附加要求的优先级队列，一个查找/搜索功能，它将告诉一个项目是否在队列中的任何位置。所以函数将是：insert、del-min 和 find。

我不确定是否应该使用堆或自平衡二叉搜索树。看来 PQ 通常是用堆实现的，但我想知道使用二叉搜索树是否有任何优势，因为我也需要该查找函数。

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

谢谢！

Answer 1

为什么不能只使用优先级队列和集合？当您将某些内容放入队列时，您将其添加到集合中。当您将其出队时，您将其从集合中删除。这样，设备就会告诉您队列中是否有东西。

Answer 2

如果您的查找操作相对不频繁（并且您的堆相当小），我只会进行线性搜索。如果相对频繁，或者堆很大，请考虑使用单独的数据结构或对象标志来跟踪堆成员资格（以进行“查找”测试）。外部索引的乐趣在于能够将对象放入任意多个容器中。

如果“查找”实际上是指“查找和修改”（我发现我经常需要从优先级队列中删除内容，而与典型的插入/删除分钟无关），那么以下是我使用过的三种方法

：在相当小的工作集（500-1000）上插入/删除分钟（100k/s连续）和低查找删除率（例如1/s）我对元素进行了线性搜索，然后将其从以标准方式树。

考虑到较高的插入/删除率以及相当频繁的查找删除，我在间接找到已删除的对象后将其标记为“无趣”。实际的释放被推迟到对象正常出队为止。

给定一个小的 std::priority_queue （除了 insert/del-min 之外没有访问方法），只有几个元素和相当不频繁的删除，我只是将整个队列复制到临时 std::vector 并复制修改/所需的部分回到队列中。然后我就哭着睡着了。

Answer 3

如果您需要多种数据结构的优势，那么您可以在组合中使用它们。
例如，如果您需要优先级队列和二叉搜索树的优势，那么可以对它们执行所需的操作。

如果是 insert 则将元素插入到它们两个中。

如果是find，那么您可以使用二叉搜索树找到该元素，如果找到，则继续在优先级队列中查找它。

如果它是 min ，那么首先将其从优先级队列中删除，现在您知道它是哪个元素，然后您可以将其从二叉搜索树中删除。

如果是del，那么首先在二叉搜索树中找到它并删除它，然后继续在优先级队列中找到它并从那里删除它。

假设二叉树的节点和优先级队列的节点是指向元素的指针。

Answer 4

IIRC 在堆上的搜索/查找是 O(n) 而在树上则是 O(log(n)) 并且其他标准 PQ 操作是相同的。

堆只是在经验上通过某些恒定因素更有效，因此如果它是一个大队列，那么树应该更好，如果它很小，则需要测试和分析。从理论上知道什么更快是件好事，但如果这些常数因子很大，那么对于足够小的数据集可能完全无关。

Answer 5

具有 min-heap 属性的基数树将提供您需要的属性。这实际上将为您的操作提供恒定的时间复杂度。例如，如果我们查看 这个 Haskell 实现，您提到的所有三个操作的时间复杂度都是O(min(n,W))。其中 n 是元素数量，W 是 int 中的位数（32 或 64）。

Answer 6

请检查此代码。我编写了这个程序，这是一个包含您所需功能的优先级队列。

1. Insert
2. Find
3. Delete
4. Show

你可以尝试一下。它工作得很好。这里我将升序的最小数添加到最大数。

我使用优先级队列默认函数来通过 switch case 来完成此操作。

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;
}

Answer 7

首先介绍一些背景知识。堆通常以数组或向量的形式实现，其中每个节点都有一个索引，其中 0 是最高优先级的节点。

您的堆必须为每个节点存储各种数据：值、回调函数等等。

实际上，不断移动这些节点的成本太高，因此它们往往被分配在堆向量之外，堆向量实际上是指向节点的指针数组。

一般来说，我会让优先级队列的 API 为您提供指向相关节点的指针，并实现一个以该节点的地址作为参数的 delete() 方法。实际上，应用程序要求按优先级（在我的例子中是时间）注册一个事件，并获得一个不透明的“cookie”。如果应用程序想要取消该事件，他们会将该 cookie 传回堆中。

好的，现在回答你的问题！这个节点（cookie）应该保存节点在向量中的索引。这允许 delete() 操作直接转到向量中的该点。然后，您可以交换该节点的堆尾部，并根据需要向上或向下重新堆化。

Answer 8

将数据存储在您测试过的最快容器中，并使用布隆过滤器来测试容器中是否有某些内容。

我在之前的项目中将布隆过滤器与哈希表配合使用，它在平均包含大约 10k 项的哈希表上将速度提高了 400 倍。

布隆过滤器有一些有趣的属性：

• 如果布隆过滤器的答案是否定的，那么它是 100% 可靠的。
• 如果答案是肯定的，则需要检查其他数据
  结构以确保该项目确实存在。
• 确保你选择了一个好的哈希函数:)