私は、アイテムがキュー内のどこかにあるかどうかを通知する検索/検索機能という要件を追加したプライオリティ キューの実装を検討しています。したがって、関数は次のようになります。insert、del-min、find です。
ヒープと自己平衡二分探索木のどちらを使用するべきかわかりません。PQ は通常、ヒープで実装されているようですが、検索機能も必要なので、二分探索木を使用する利点があるかどうか疑問に思っています。
さらに、平均して、削除よりも挿入の方が多くなります。d-ary heapも検討しています。基本的に、毎秒が重要です。
ありがとう！
Priority Queue と Set だけを使用できないのはなぜですか? 何かをエンキューすると、それをセットに追加します。デキューすると、セットから削除されます。そうすれば、セットは何かがキューにあるかどうかを教えてくれます。
検索操作の頻度が比較的低い (そしてヒープがかなり小さい) 場合は、単純に線形検索を実行します。比較的頻繁に発生する場合、またはヒープが巨大な場合は、別のデータ構造またはオブジェクト フラグを使用してヒープ メンバーシップを追跡する (「検索」テストを実行する) ことを検討してください。外部インデックス作成の利点は、オブジェクトを好きなだけコンテナーに入れることができることです。
「検索」が本当に「検索と変更」を意味する場合 (通常の挿入/デルミンとは別に、優先キューから何かを削除する必要があることがよくあります)、私が使用した 3 つのアプローチを次に示します。
かなり小さい作業セット (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操作は同じです。
ヒープは経験的に一定の要因によってのみ効率的であるため、キューが大きい場合はツリーの方が優れているはずであり、キューが小さい場合はテストとプロファイルを行う必要があります。理論的には何が速いかを知ることはすべて良いことですが、これらの定数係数が大きい場合、十分に小さいデータセットにはまったく関係がない可能性があります。
Radix trees with a min-heap property will provide the properties you need. This will actually give you constant time complexities for your operations. For example, if we look at this Haskell implementation, all three operations you mention have time complexity O(min(n,W)). Where n is the number of elements, and W is the number of bits in an int (32 or 64).
このコードを確認してください。このプログラムをコーディングしました。これは、必要な機能を備えた優先キューです。
1. Insert
2. Find
3. Delete
4. Show
あなたはそれを試すことができます。それは完全に機能しています。ここでは、昇順の最小数を最大数に追加しました。
優先キューのデフォルト機能を使用して、switch ケースでそれを行いました。
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;
}
テストした最速のコンテナーにデータを保存し、ブルーム フィルターを使用してコンテナー内に何かがあるかどうかをテストします。
以前のプロジェクトでブルーム フィルターとハッシュ テーブルを組み合わせたところ、平均約 10,000 アイテムのハッシュ テーブルで 400 倍高速化されました。
ブルーム フィルターには、いくつかの興味深いプロパティがあります。