heap sortを使った上位ランキング取得プログラム - 遥かへのスピードランナーManaging Gigabytes 4.6章で解説されているソートのプログラムを実装してみた。 検索エンジンなどでN個のデータの中から上位r個を取得したい場合、まずN個のデータからなるmax-heapを構成して、ルート（最大値）から順にr個をヒープから取り除くというアプローチが考えられる。しかしN>>rの場合、r個のデータからなるmin-heapを構成して、残りのN-r個のデータをheapのルート（最小値）と順次比較して、ルートよりも大きい場合はルートと入れ替えて、heapを再構成する、という手順を取った方がより計算量が少なくて済む、という話。 10万件のランダムな数値をスペース区切りで出力するプログラム #include <iostream> #include <stdlib.h> using namespace std; int main (int argc, char *argv[
