部分ソート(2)

　実は、libstdc++のpartial_sort（破壊的操作を行う方）は、部分ソート(1)で紹介したようなアルゴリズムにはなっていなかった。次の様になっている。
　先頭のm個の要素を使ってヒープを作る。そこから最後までは、ヒープの最初の要素(つまりルート)と配列の一番最初の要素を比較して、先頭要素よりも小さければheapのなかに突っ込む、という操作を最後まで繰り返す。終わったら最後に最初のm個分をソートして終了。以下のコードはgcc-4.1.1の/libstdc++-v3/include/bits/stl_algo.hから引用した。

      std::make_heap(__first, __middle, __comp);
      for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
	if (__comp(*__i, *__first))
	  std::__pop_heap(__first, __middle, __i, _ValueType(*__i), __comp);
      std::sort_heap(__first, __middle, __comp);

　__pop_heapという操作しか見えず、これでなんでヒープの要素数がmに保たれるのか一見するとよくわからないが、コードを眺めたりドキュメントを眺めてみたりした感じでは、どうも__firstと__iが交換されているようだ。（もちろん、その後でヒープ条件を保つように、配列の先頭m個はまた並べ替えられる。）つまり、pop_heapと__pop_heapは同じではないというところに注意しないといけない。（pop_heapは中で__pop_heapを呼び出している。）
　計算コストを考えると、m個のヒープを作るのがm、先頭要素よりも小さいかどうかを判定するコストはn - m, 小さかった場合にヒープに突っ込むという操作はlog m。ただし、このlog mの操作は毎回起こる訳ではない。というわけで、m + (n - m) + (n - m)* / 2 log mで、計算量はたぶんn log mになるだろう。(1)で紹介した方法はn + m log nであったので、メモリに余裕があればpartial_sort_copyを使う方が速いことがわかる。あと、最初に全ての要素に関して知っている必要がないので、オンラインな問題設定の場合にも有利だ。（あんま部分ソートかつオンラインの問題例を思い付かないけど。）