いつでも、数量に基づいて上位k製品を伝える必要があります

Question

データの流れがあります。 データには商品IDと数量が含まれています。 いずれの場合も、数量に基づいて上位k製品を伝える必要があります。

私のアプローチ：

値としてキーと製品の量、ヒープ指標とし​​て製品IDを格納する1つのハッシュマップを更新サイズk の一つのminheapを維持します。

これで、1つのデータが受信されました。製品IDがハッシュマップに存在するかどうかを確認します。

ハッシュマップ中に存在する場合：

更新（製品数量が増加されるように）ヒープ内の製品数量。 更新ハッシュマップ

に新しい数量、新しいインデックスをハッシュマップに存在しない場合：それが大きければ、ヒープのルートを削除し、 新製品の量がヒープに最小値よりも大きいか否か

チェック新しい価値で置き換えてください。

問題： 私のアプローチの問題は、製品数が増加するためいつでも製品IDを繰り返すことができるということです。 現在、いくつかの製品がヒープにないかもしれないが、将来ヒープの一部になる可能性があるため、製品数量とヒープインデックスの両方を保存できるように私はどのようなアプローチをとるべきですか？

Answer 1

すべての製品とその数を格納するのに十分なメモリがある場合は、製品IDでキー付けされたハッシュマップと、頻度順に並べられたツリー構造（たとえばAVL tree）を維持します。

更新が入って来：製品はハッシュマップにない場合は

• 、ハッシュマップに追加し、製品の場合は1
• の周波数でツリーに追加ハッシュマップに既にあり、ツリーでそれを調べ、頻度を上げて、ツリー内のノードの位置を調整します。

ノードをツリーに追加し、ノードの位置を調整するのは、O（ログn）操作です。

トップ 'k'製品を頻度別に取得する必要がある場合は、ツリーのインオーダートラバーサルを使用して、早めにkに到達します。

すべての製品のカウントを格納するメモリがない場合は、少し複雑になり、おそらく近似アルゴリズムを使用する必要があります。 https://cstheory.stackexchange.com/questions/19802/top-k-frequent-items-in-data-streamにはそれに関するいくつかのアイデアがあります。