次の並べ替えシナリオがあります。
ソートされていないデータを含む入力配列が与えられた場合: 1、5、2、6、9
a）9、6、5、2、1の降順で並べ替えます
b) 現在のソート済みリストの最大値 9 を出力に送信します
c) 残りの値の一部を変更します。つまり、5 は 10 になり、1 は 3 になります。
d) ソートされたリストの残りを 10、6、3、2 に更新する
e) すべての未訪問の値が出力に送信されるまで、b) から繰り返します (これらの値は、送信されるたびに更新される可能性があります)。
このシナリオを使用できるアプリケーションまたは特定の問題の種類を知っている人はいますか? 最適なアルゴリズムは、更新された大量のデータを挿入および削除する代わりに、2 つのリンクされたリストを使用してインデックスを交換することですか? ありがとう
これはある種のプライオリティ キューのように聞こえます。特定の時点で最も優先度の高いものが処理され、キューから削除されます。他の要素の優先順位が変更され、キュー内で前後に移動する可能性があります。
リストが大きく (パフォーマンスについても考える価値がある)、要素の総数に比べて更新された要素の数がかなり少ないと仮定すると、すべての変更されていない要素が並べ替えられ、変更されたと見なされるクイックソートを使用することをお勧めします。アルゴリズムの規定に従って要素が挿入されます。
要素のサイズが関連しており、数値だけでなく、アルゴリズムとは無関係に、実際の要素ではなく、それらへの参照またはポインターをソートしたい場合があります。
追加の操作で優先キューを使用できます: キーの変更。ダイクストラ アルゴリズムの実装に使用できます。基礎となるバイナリ ヒープを使用したこのようなデータ構造については、たとえば、Robert Sedgewick の著書「Algorithms in C++/C/Java」で説明されています。
あなたが探しているのはHeap( http://en.wikipedia.org/wiki/Heap_(data_structure) )と呼ばれ、C++/STLで実装されており、関数priority_queueもあります( http://www.cplusplus. com/reference/algorithm/push_heap/ ) 配列で動作します。push_heappop_heap
挿入/削除/更新のヒープの複雑さを使用する場合はO(logN)であり、最大要素の取得はO(1)であるため、ニーズに最適です。