21

k番目に大きい要素の高速検索をサポートするキューデータ構造を必要とする問題に直面しています。

このデータ構造の要件は次のとおりです。

  1. キュー内の要素は必ずしも整数である必要はありませんが、互いに比較可能である必要があります。つまり、2つの要素を比較すると、どちらが大きいかがわかります（同じでもかまいません）。

  2. データ構造は、エンキュー（末尾の要素を追加）およびデキュー（先頭の要素を削除）をサポートする必要があります。

  3. キュー内でk番目に大きい要素をすばやく見つけることができます。plsnotekは定数ではありません。

  4. エンキュー、デキュー、およびk番目に大きい要素の検索操作はすべて同じ頻度で発生すると想定できます。

ここに画像の説明を入力してください

私の考えは、修正された平衡二分探索木を使用することです。このツリーは、すべてのノードiが別のフィールドn iで拡張されていることを除いて、通常の平衡二分探索ツリーと同じです。niは、ルートノードiを持つサブツリーに含まれるノードの数を示します。前述の操作は次のようにサポートされます。

簡単にするために、すべての要素が異なると仮定します。

Enqueue（x）：xが最初にツリーに挿入され、対応するノードがノードtであると仮定して、pair（x、pointer to node t）をキューに追加します。

デキュー：（e1、ノード1）が先頭の要素であり、ノード1がe1に対応するツリーへのポインターであるとします。ツリーからノード1を削除し、キューから（e1、ノード1 ）を削除します。

K番目に大きい要素の検出：ルートノードがノードルートであり、その2つの子がノード左とノード右（すべて存在すると仮定）であると仮定すると、Kをnルートと比較します。3つのケースが発生する可能性があります。

  1. K <nが残っている場合、nルートの左側のサブツリーでK番目に大きい要素が見つかります。

  2. K> n root -n rightの場合、 nrootの右側のサブツリーで（Kn root + n right）番目に大きい要素が見つかります。

  3. それ以外の場合、nルートは必要なノードです。

3つの操作すべての時間計算量はO（log N）です。ここで、Nは現在キューにある要素の数です。

上記の操作を高速化するにはどうすればよいですか？どのようなデータ構造とどのように？

4

3 に答える 3

9

注-すべての人にとってそれ以上の成果を上げることはできませんO(logn)。せいぜい、最も気になる操作を「選択」する必要があります。（それ以外の場合はO(n)、配列をDSにフィードし、1番目、2番目、3番目、... n番目の要素をクエリすることで並べ替えることができます）

  • ソートされた構造としてBalancedBSTの代わりにスキップリストを使用すると、デキューの複雑さをO(1) 平均的なケースに減らすことができます。他の操作の複雑さには影響しません。
    スキップリストから削除するには、キューの先頭からポインタを使用して要素にアクセスし、リンクをたどってそれぞれを削除するだけです。削除する必要のあるノードの予想数は1+1/2 + 1/4 + ...=2です。
  • O(logK)Kthを見つけるには、（ルートではなく）左端のノードから開始し、「必要な息子が増える」ことがわかるまで進み、見つかったノードをルートとして扱います。質問。漸近的な複雑さの方が優れていますが、定数係数は2倍です。
于 2012-09-21T15:21:06.117 に答える
2

面白い論文を見つけました：

VLDB 2008で公開され、71によって引用された、不確実なストリームに関するスライディングウィンドウTop-kクエリ。

https://www.cse.ust.hk/~yike/wtopk.pdf

VLDBはデータベース研究分野で最高の会議であり、引用数はデータ構造が実際に機能していることを証明しています。

この論文はかなり難しいように見えますが、データ構造を本当に改善する必要がある場合は、この論文またはこの論文のリファレンスページにある論文を読むことをお勧めします。

于 2012-09-21T15:29:44.037 に答える
1

フィンガーツリーを使用することもできます。

たとえば、優先キューは、ツリー内の子の最小優先度で内部ノードにラベルを付けることで実装できます。また、インデックス付きリスト/配列は、子の葉の数でノードにラベルを付けることで実装できます。フィンガーツリーは、償却されたO（1）の短所、反転、cdr、O（log n）の追加および分割を提供できます。インデックス付きまたは順序付けられたシーケンスに適合させることができます。

また、純粋に機能的な構造であるため、これは同時使用に適しています。

于 2012-09-27T04:55:07.000 に答える