Python - 「ランクリスト」がありますか？1つ実装する必要があります

Question

最高のランタイムでその構造を管理し、そのランキングでXオブジェクトを格納できるデータ構造を使用します。

これをRank_List()とします。 X = 2を定義すると、次のようになります。 obj1がより高いランク付けされ、別のオブジェクトを追加した後

ranked_list = Rank_List() 
ranked_list.add((obj1, 0.5) 
print ranked_list -> [(obj1, 0.5)] 

ranked_list.add((obj2, 0.75)) 
print ranked_list -> [(obj2, 0.75), (obj1, 0.5)] 

だから我々はそれが（最初の場所にあり、0.5は第二である0.75）のチェックにランクを保持見ることができます

ranked_list.add(obj3, 0.7) 
print ranked_list -> [(obj2, 0.75), (obj3, 0.7)] 

、 obj1はリストからキャストされます（X = 2）ので、最大2個のオブジェクトしかリストに格納されません。

すでにPythonに存在するようなデータ構造はありますか？ 最良のランタイム結果を得るにはどの方法で実装すればよいですか

Answer 1

コメントから、シーケンスから上位K個の要素を抽出することを検討しています。その場合、リストを並べ替える必要はありません。 ヒープキューを使用できます。

heapqは、すべての親がその子のいずれよりも小さい値を持つバイナリツリーです（値を反転すると、より大きい値）。これは、O（K）時間内に常に上位のK要素を見つけることができることを意味しますが、挿入時にヒープを順番に保つことは、O（logN）時間だけかかります。合計で、N個のアイテムが入り、K個のトップアイテムが出てくる（順番に）ため、これは非常に効率的なO（KlogN）アルゴリズムを提供します。

Python標準ライブラリにはheapq moduleが含まれています。

ヒープを自分のままにするか、heapq.nlargest functionを使用して、繰り返し可能なものからヒープを作成し、上位のK個のアイテムを直接返すことができます。あなたの次をプッシュする、（(priority, elem)タプルとして）最初のK個の要素のリストを作成し、手動で保持ヒープにKに最大アイテムを保持、それはそのサイズに達するとheapify()を使用して、そこから出て使用heapreplace() ONに

要素をリストに追加し、が最小のを削除します。そうすることで、K個の最大アイテムの固定サイズのヒープを常に保つことができます。最後に、sorted(heap, reverse=True)を使用して、逆順ソート順（最も大きいものから最も小さいものまで）のそれらの最大アイテムを表示します。