c++ - 配列を部分的にソートする

Question

部分的な並べ替えは、std::partial_sortを使用して実行できます。

部分的なソート手段

5 7 4 2 8 6 1 9 0 3

3つの要素を部分的に並べ替えた後

0 1 2 7 8 6 5 9 4 3

http://en.cppreference.com/w/cpp/algorithm/partial_sort。

ただし、一部の要素がすでに並べ替えられている場合は最適ではありません。

そうして、部分的にソートされた配列を利用できる他のそのような関数はありますか？

Answer 1

ストリーミング メディアンアルゴリズムの適応を使用して、k項セットの最小項を追跡できます。std::priority_queue最小および最大ヒープに使用できます。

アルゴリズムは次のように機能します。

• 最大ヒープは、k最小の用語を保持するために使用されます
• 最小ヒープは、他のすべての用語を保持するために使用されます
• 追跡する用語ごとに、追加するヒープを決定し、そこに追加します
  • k最大ヒープのサイズがそこに追加するよりも小さい場合、そうでない場合
  • 項が最大ヒープの先頭よりも小さい場合はそこに追加し、そうでない場合はそこに追加します
  • 項を最小ヒープに追加します
• 最大ヒープの最上位に複数のk用語がある場合は、最上位の用語を取り出して最小ヒープにプッシュします

用語をソートする必要がある場合は、それらを最大ヒープから降順でポップし、逆の順序で配列に配置して、ソートされた配列を残すことができます。コンテナーを最大ヒープのコンストラクターに渡した場合は、コンテナーをコピーして並べ替えることができます。

デフォルトではstd::priority_queue最大ヒープです。最小ヒープにするには、テンプレート パラメーターの一部を変更します。

typedef std::priority_queue<int> MaxHeap;
typedef std::priority_queue
    <
        int,
        std::priority_queue<int>::container_type,
        std::greater<int>
    > MinHeap;