修行の場

知人が言っていました。これは修行だと。

連想配列とヒープを少し真面目に見る

背景

ヒープや連想配列は汎用性が高いデータ構造です。 少し真面目に見る価値はあると思うので中身を見ていきます。

C++GCCPythonはCPythonを見ていきます。

順序付き連想配列

アルゴリズム

C++のstd::map, std::setはred-black treeで実装されています。 Red-black treeはbinary treeの一種でself-balancingな木とのことです。 ちなみにpythonのdictはinsert順を保存するのみでキーによるソートはされません。

self-balancingの効率と最悪ケースのunbalancingの度合いを下げるようにノードに色をつけることでworst caseでO(logn)の探索、更新、削除なっています。rebalancingもO(logn)で、かなり安定したアルゴリズムと捉えられます。色は二色なのでノード数nでnビットの追加程度で住むとのことです。さらに小さい順、大きい順のtraverseも効率よくできます。

red-black treeでは、根から葉までの最も短い距離と最も長い距離の関係は最短*2<=最長となるようで、その程度の平衡が保たれるようです。

To see why this is guaranteed, it suffices to consider the effect of properties 4 and 5 together. For a red–black tree T, let B be the number of black nodes in property 5. Let the shortest possible path from the root of T to any leaf consist of B black nodes. Longer possible paths may be constructed by inserting red nodes. However, property 4 makes it impossible to insert more than one consecutive red node. Therefore, ignoring any black NIL leaves, the longest possible path consists of 2B nodes, alternating black and red (this is the worst case). Counting the black NIL leaves, the longest possible path consists of 2B-1 nodes.

さっくりまとめると、根から葉までの黒ノードの数は同じでなければならない。となると、赤ノードを追加するしかないが、赤ノードは黒ノードと同数しか追加できないので、最長は最短の二倍以上にはなれない。とのことです。

応用例

このデータ構造であれば、範囲検索が必要な場合もO(logn)程度で住みます。 構築コストは高そうですが、ノードをあとから追加しても順序が保証されたりするメリットはあり、データベースのインデックスとしても使えそうです。MySQLなんかはBツリーですが...

Wikipediaにかかれているものだと、

に使っているようです。 今後、AVL TreeやWAVL Treeとの比較とか詳しく見てもいいかもしれません。

ヒープ

C++priority_queuePythonheapqの実装を見てみます。 heapqもpriority_queueも最も小さい要素の取得がO(1)という実装になっています。 insert, deleteはO(logn)とのことです。キーの更新もO(logn)とのことです。

ヒープツリー

heapqは配列で実装されていて、binary heap treeのようです。 追加のみ、削除更新しない、ランダムアクセス多いと考えると良いチョイスです。

heapの詳細はwikipedia)が詳しいです。binary search treeと比較して、上下関係は保証されるが、横の関係は定義されていなく、最大・最小要素を連続的に取っていくような用途に適しているようです。

応用例

名前の通り優先度つきのキューの実装に使えます。 実装するには安定性のためにtupleではなく、独自クラスを作ったりすれば良くて、 キューの削除や優先度の変更。削除更新はヒープの再構築が必要になるためフラグなどで対応する例が挙げられていました。

確かに他の方法だと、 例えば、配列を常にソートしていて、追加時にbinary searchで追加箇所を探して追加。 最小要素取り出し時は[0]を取り出して削除とかだと。 配列なら追加削除でメモリの移動にO(n), 連結リストで実装すると、追加がO(nlogn), 取り出しがO(1)になる。

追加、取り出し双方O(logn)でバランスが良い。 また、最小値を参照するだけなら、O(1)になり、かなり速いので、 そういったケースに使うのが良いと思います。