9

これまでに挿入された最大のアイテムを常にn(順不同で) 保持するデータ構造が必要です。

したがって、nが 3 の場合、いくつかの数字を挿入すると、コンテナーの内容が変更される次のセッションを作成できます。

[]  // now insert 1
[1] // now insert 0
[1,0] // now insert 4
[1,0,4] // now insert 3
[1,4,3] // now insert 0
[1,4,3] // now insert 3
[4,3,3]

あなたはアイデアを得る。データ構造の名前は何ですか? これを実装する最良の方法は何ですか? それとも、これはいくつかのライブラリにありますか？

priority_queue逆比較を使用popするため、最小の要素を削除する要素 (委任)を持つコンテナーを使用することを考えています。そのため、insert関数は最初に、挿入される新しい要素が最小の要素よりも大きいかどうかを確認します。もしそうなら、その最小のものを捨てて、新しい要素をプッシュします。

（私はC++実装を念頭に置いていますが、それでも問題は言語に依存しません。）

4

8 に答える 8

14

必要な特定のデータ構造は、おそらく暗黙的なヒープです。生のデータ構造は単なる配列です。便宜上、サイズが N=2^n 要素であり、最大の N-1 要素を維持したいとします。

アイデアは、配列 (A と呼ぶ) を深さ n の完全なバイナリ ツリーとして扱うことです。

  • A[0] を無視します。A[1] をルート ノードとして扱います
  • 各ノード A[k] の子ノードは A[2*k] と A[2*k+1] です。
  • ノード A[N/2..N-1] は葉です

ツリーを「ヒープ」として維持するには、各ノードがその子より小さい (または等しい) ことを確認する必要があります。これは「ヒープ状態」と呼ばれます。

  • A[k] <= A[2*k]
  • A[k] <= A[2*k+1]

ヒープを使用して最大の N 要素を維持するには:

  • ルート A[1] はヒープ内の最小要素であることに注意してください。
  • 新しい各要素 (x) をルートと比較します。それが小さい場合 (x<A[1])、それを拒否します。
  • それ以外の場合は、次のように新しい要素をヒープに挿入します。
    • ヒープからルート (A[1]、最小の要素) を削除し、それを拒否します。
    • それを新しい要素に置き換えます (A[1]:= x)
    • 次に、ヒープ状態を復元します。
      • x が両方の子より小さいか等しい場合、完了です
      • それ以外の場合は、x を最小の子と交換します
      • ヒープ条件が満たされるまで、新しい位置ごとにテストとスワップを繰り返します

基本的に、これにより、置換要素が自然な場所に到達するまでツリーを「フィルタリング」します。これには、最大でも n=log2(N) のステップが必要です。また、ツリーの暗黙的な形式により、非常に高速な実装が可能になります。既存の境界優先キュー ライブラリは、ほとんどの場合、暗黙的なヒープを使用します。

于 2009-02-19T06:50:34.757 に答える
5

Javaでは、TreeSetなどによって実装されたSortedSetを使用できます。挿入するたびに、セットが大きすぎるかどうかを確認し、大きすぎる場合は最後の要素を削除します。

これはかなり効率的です。私はいくつかのプロジェクトオイラーの問題を解決するためにこれをうまく使用しました。

于 2009-02-19T07:30:58.963 に答える
4

priority_queue は C++ で STL に最も近いものです。別のクラスでラップして、サイズを自動的にトリミングする独自の実装を作成できます。

言語に依存しない (メモリの断片化に安全ではないかもしれませんが):

  1. データの挿入
  2. 選別
  3. n 番目の要素以降をすべて削除

std::priority_queue はステップ 2 を実行します。

于 2009-02-19T06:15:23.780 に答える
2

限定されたプライオリティ キューだと思います... Java の標準ライブラリには、このようなものがあります。編集：それは呼ばれていLinkedBlockingQueueます。C++ STL に同様のものが含まれているかどうかはわかりません。

于 2009-02-19T06:07:08.917 に答える
1

ソートされたコレクションから最初のn個の要素だけを取得することはできませんか？

于 2009-02-19T07:30:42.333 に答える
1

Python では、heapq を使用します。次のような小さなラッパーを作成します。

class TopN_Queue:
    def __init__(self, n):
        self.max_sz = n
        self.data = []

    def add(self, x):
        if len(self.data) == self.max_sz:
            heapq.heappushpop(self.data, x)
        else:
            heapq.heappush(self.data, x)

...

于 2018-09-28T03:44:43.223 に答える
0

はい、サイズ N の最小ヘッドを維持できます。次に、挿入ごとに新しいアイテムとルート アイテムを比較します。ルートをポップし、ルートより「大きい」場合はアイテムを挿入します。最終的に N 個の最大アイテムになります。

于 2012-11-21T07:46:11.880 に答える
-1

最小ヒープを作成し、カウンターも格納します。

カウンターに到達したときはいつでも; 抽出-分。

これは、O（1）insert、get-min、およびO（log log n）extract-minで実行できます。[1]または、O（log n）insertとO（1）を使用してこれを行うこともできます。[2]

[1]M. Thorup、「定数時間の減少キーと単一ソース最短経路問題を伴う整数優先キュー」、コンピューティング理論に関する第35回ACMシンポジウムの議事録、ニューヨーク、ニューヨーク、米国、2003年、149ページ–158。

[2]GS Brodal、G。Lagogiannis、C。Makris、A。Tsakalidis、およびK. Tsichlas、「ポインターマシンの最適なフィンガーサーチツリー」、J。Comput。Syst。Sci。、vol。67、いいえ。2、pp。381–418、2003年9月。

于 2013-01-05T09:30:13.943 に答える