ネタ元 → わんくま東京勉強会懇親会
Rの発言:
「ソートする時にさ、はじめにいっぺんデータを頭からなめて
偏り具合とかバラつき具合を調べておいて、最良のソートアルゴリズムを
選んで...」
これに周りのやつらが噛みつく:
「そんなもん、データ読み込むたんびにソートしとけば全部読み終わった
ときゃソート終わってんぢゃん」
R少なからず凹んだ様子。
"データ読み込むたんびにソート"の代表的な例が binary-tree や B-tree です。
が、もひとつ heap てーのがあります。heap だとデータ読み込むたんびに
半分ソートした状態を作ります。なんたらtree と違い、枝のポインタ(参照)
を必要としないのでコンパクトなのが売り。
indexを1から始めた可変長配列を用意します。
この配列 array[] に格納された要素は:
array[i] を親、array[i*2] と array[i*2+1] を子としたとき、
任意の親に対し、その二人の子より小さくない。
つまり
array[1] はその子: array[2],array[3] 以上、
array[2] はその子: array[4],array[5] 以上、
array[3] はその子: array[6],array[7] 以上、
array[4] はその子: array[8],array[9] 以上、
... てことになり、 つまるところ先頭要素 array[1] が最大要素となります。
この状態をヒープ状態と呼びましょう。
N-1個の要素が詰まったヒープに要素を追加するには:
- 末端に array[N] を追加する。
- array[N]の親array[N/2]と比較し、親<=子だったら入れ替える
- 親子を入れ替えちゃったらさらにその上位の親子の大小関係が狂う
かもしれないので同様に比較/交換する。
親子の交換が起こらなくなるまで繰り返す。
この処理は多くともlog2(N)の回数で終了します。
これを繰り返し、全要素を突っ込んだところで
ヒープ状態:"半分ソートされた状態"ができあがります。
ではソート。先頭要素が一番大きいことがわかってます。
こいつを取り出し、代わりに末端要素を入れちゃいます。
そうすると親子の大小関係が変化します。
自分と二人の子を比べ、一番大きいやつを新たな親として親子を入れ替えます。
そーすっと入れ替わった子と、さらにその子たちとのあいだで大小関係が狂うかも。
なので同様の処理を繰り返し、親子の交換が起こらなくなったら終了、
ヒープ状態が維持されます。
ほんでもって、再び先頭要素を取り出して...配列が空になるまで繰り返します。
要するに要素の大きな順で取り出すことができてます。ほらソートできた。
STL/CLRでこの様子を再現してみた。
#include <cliext/algorithm>
#include <cliext/vector>
using namespace System;
using namespace cliext;
int main() {
Random r;
vector<int> v;
Console::WriteLine("前半");
for ( int i = 0; i < 10; ++i) {
int n = r.Next(10,50);
Console::Write("{0} -- ", n);
v.push_back(n);
push_heap(v.begin(), v.end());
for each ( int item in v ) {
Console::Write("{0} ", item);
}
Console::WriteLine();
}
Console::WriteLine("後半");
for ( int i = 0; i < 10; ++i ) {
int n = v.front();
Console::Write("{0} -- ", n);
pop_heap(v.begin(), v.end());
v.pop_back();
for each ( int item in v ) {
Console::Write("{0} ", item);
}
Console::WriteLine();
}
}
---- 実行結果 ----
前半
18 -- 18
19 -- 19 18
11 -- 19 18 11
13 -- 19 18 11 13
12 -- 19 18 11 13 12
47 -- 47 18 19 13 12 11
39 -- 47 18 39 13 12 11 19
14 -- 47 18 39 14 12 11 19 13
41 -- 47 41 39 18 12 11 19 13 14
26 -- 47 41 39 18 26 11 19 13 14 12
後半
47 -- 41 26 39 18 12 11 19 13 14
41 -- 39 26 19 18 12 11 14 13
39 -- 26 18 19 13 12 11 14
26 -- 19 18 14 13 12 11
19 -- 18 13 14 11 12
18 -- 14 13 12 11
14 -- 13 11 12
13 -- 12 11
12 -- 11
11 --