ここで問題が発生し、次の3つの操作でO（lg n）の最悪の場合をとるデータ構造を設計する必要があります。
a) Insertion: Insert the key into data structure only if it is not already there.
b) Deletion: delete the key if it is there!
c) Find kth smallest : find the ݇k-th smallest key in the data structure
ヒープを使うべきかどうか疑問に思っていますが、それについてはまだ明確な考えがありません。
O（lg n）の最初の2つの部分を簡単に取得できます。さらに高速ですが、c）の部分の処理方法がわかりません。
誰でもアイデアを共有してください。
2つの解決策が思い浮かびます。
バランスの取れた二分探索木を使用します（赤黒、AVG、スプレーなど）。すでに操作（1）と（2）に精通しています。操作（3）の場合、各ノードに追加の値、つまりそのサブツリー内のノードの総数を格納するだけです。この値を使用して、O（log（n））でk番目に小さい要素を簡単に見つけることができます。たとえば、ツリーが次のようになっているとします。ルートAには10ノード、左の子Bには3ノード、右の子Cには6ノード（3 + 6 + 1 = 10）があり、8番目に小さい要素を見つけたいとします。あなたはあなたが右側に行くべきであることを知っています。
スキップリストを使用します。また、平均してO（logn）のすべての（1）、（2）、（3）操作をサポートしますが、実装には少し時間がかかる場合があります。
データ構造で要素が並べ替えられている場合は、k番目に低い要素を簡単に見つけることができます。
検索と挿入のための二分探索木の最悪の場合のコストはO（N）であり、平均的な場合のコストはO（lgN）です。
したがって、検索と挿入の両方でO（lgN）の最悪の場合の複雑さを保証する赤黒二分探索木を使用することをお勧めします。
赤黒木について詳しくはこちらをご覧ください。また、Javaでの赤黒BSTの実装についてはこちらをご覧ください。
したがって、上記の赤黒BST実装を使用してk番目に小さい要素を見つけるという点では、kの値を渡してselectメソッドを呼び出す必要があります。selectメソッドは、最悪の場合のO（lgN）も保証します。
解決策の1つは、クイックソートの戦略を使用することです。
ステップ1：ピボット要素として最初の要素を選択し、正しい場所に移動します。（最大n回のチェック）この要素の正しい場所に到達したら、チェックを実行します
ステップ2.1：location> kの場合、要素は最初のサブリストにあります。したがって、2番目のサブリストには関心がありません。
ステップ2.2ifロケーション
ステップ2.3location== kの場合、要素がルック/再帰を壊します
ステップ3：適切なサブリストを使用して、ステップ1から2.3を繰り返します。
このソリューションの複雑さはO（n log n）です。
ヒープは、配列のK番目に小さい要素を見つけるための適切な構造ではありません。これは、K番目の要素に到達するためにヒープからK-1要素を削除する必要があるためです。
中央値の中央値アルゴリズムに依存する、K番目に小さい要素を見つけるためのはるかに優れたアプローチがあります。基本的に、どのパーティションアルゴリズムでも平均して十分ですが、中央値の中央値には、中央値を見つけるための最悪の場合のO（N）時間の証明が付属しています。一般に、このアルゴリズムは、中央値だけでなく、特定の要素を見つけるために使用できます。
C＃でのこのアルゴリズムの分析と実装は次のとおりです。ソートされていない配列でK番目に小さい要素を見つける
PS関連する注意点として、アレイを使用してインプレースで実行できることはたくさんあります。配列は素晴らしいデータ構造であり、特定の状況でその要素を整理する方法を知っている場合にのみ、追加のメモリを使用せずに非常に高速に結果を得ることができます。
ヒープ構造は非常に良い例であり、QuickSortアルゴリズムでもあります。そして、これが配列を効率的に使用する本当に面白い例の1つです（この問題はオリンピックのプログラミングに起因します）：配列内の多数決要素を見つける