habrには、セグメントツリー、duchaなど、多くの興味深いデータ構造の説明があります。 複雑なデータ構造に興味があるなら、catへようこそ！ 私の記事シリーズでは、さまざまなタイプのヒープと、それらを実行する方法について説明します。
1） 二項パイル
2） 左ヒープ
3） フィボナッチ束
4） これらのデータ構造を実践する
問題文：
オブジェクトの多くが（タスクによって異なる）格納されるデータ構造を構築するために、各オブジェクトにはキーフィールドがあり、それによって最小要素をすばやく見つけることができます。 この構造では、次の操作が可能です。
Make
新しい空のヒープを作成し、
Insert
-ヒープに新しい要素を挿入し、
Minimum
-最小キー、
ExtractMin
最小抽出、
Merge
-2つのヒープを
Merge
し、
Decrease
-キー削減、
Delete
-オブジェクトを削除します。
多くは、配列:)やバイナリヒープなど、この構造を実装する最も簡単な方法に精通しています。 それらの単純さと一般的な知識のために、私はそれらについて詳しく説明しません。
ご存知のように、 バイナリヒープの場合 、上記の操作の漸近的な動作は次のとおりです。
Make
-O（1）
Merge
-O（N）
Insert
-O（ログN）-Nはヒープ内の要素の数です。
Minimum
-O（1）
ExtractMin
-O（ログN）
Decrease
-O（ログN）
Delete
-O（ログN）
バイナリヒープのアルゴリズムについては説明しません。Habréを含め、至る所で繰り返し説明されているからです。 バイナリヒープに慣れていない人のために、読み続ける前にバイナリヒープに慣れることをお勧めします。
次に、 二項ヒープと呼ばれるより興味深いデータ構造を考えます 。
二項パイル
二項パイルは、いくつかの制限がある二項ツリーのセットです。 少し後で紹介します。
二項ツリーは、再帰的に定義されるツリーです。
B iはB i-1であり、ツリーB i-1は根の左息子になりました。
B 0はトップです。
B 0 、B 2 、B 3の例 ：
二項ツリー（B k ）には、多くの興味深い特性があります 。
T.1。 2 kピーク
T.2。 木の高さk
T.3。 深さiのC i k頂点（これが二項と呼ばれる理由です：C i kは二項係数です）。
T.4。 ルートの子は、B、B k-2 、...、B 0-の順です。
T.5。 二項ツリーOの最大頂点の高さ（log N）
特性は帰納法によって証明されます。 木をよりよく理解するために、読者自身に証明を行うように勧めます。
それで、 二項ヒープに戻りましょう 。 二項パイルは二項ツリーのセットであり、次の制限があります。
1）各二項ツリーでは、ヒーププロパティが保持されます。
2）同じサイズの2つのツリーがない
3）ツリーはサイズ順に並べられます。
二項ヒープがプログラムにどのように保存されるかについて話しましょう。 「左の息子-右の兄弟」メソッドを使用します。 ルートリスト（
root_list
、その長さは
root_list.length
）を保存します。このリストには、二項式ツリーのルートが、高さの順に並んでいます。 各頂点には次のフィールドがあります。
data
一番上に保存されるデータ（これにより最小値が見つかります）
right
-右兄弟
child
-左の息子
degree-頂点の次数（明らかに、二項ヒープ内のツリーはこのフィールドによって順序付けられます）
すぐに気づく：
プロパティ H.1：
root_list.length
= O（log N）の長さ。Nはヒープ内の要素の数です。
証明のために、T.1のために、数値のバイナリ表記でツリーB kが存在することに注意するだけで十分です。
二項ヒープで実行できる操作の説明に移りましょう。
作る
タスク ：空のヒープを作成します。
アルゴリズム ：空の
root_list
作成します。
難易度 ：明らかに、実行時間はO（1）です。
マージ
タスク ：2つのヒープを1に結合します。
アルゴリズム ：最初に、ヒープルートリストを1つのルートリストに結合し、次数の順序を維持します。 このアルゴリズムは、mergeSortで2つの配列をマージすることに似ています。
リストの先頭へのポインターで保存し、結果のリストに最小リストを書き込みます。書き留めたリストは次のリストに移動します。 次に、受信した新しいルートリストの最初から最後まで移動し、同じサイズのツリーを1にマージします。
1）同じサイズの2つのツリーのみ。 次にそれらを結合します。
2）同じサイズの3本の木。 最後の2つを組み合わせます。
2つのツリーを結合するときは、一方のキーの方が小さいキーを見て、もう一方のツリーをこのツリーのルートの左息子にするだけで済みます。
2つのヒープを結合した後に何が起こるかの例：
難しさ ：
root_list1.length
時間O（
root_list1.length
）+ O（
root_list2.length
）=（プロパティH.1による）= O（log N）。
1つのパス（O（log N））で、結合二項ツリーを取得します。 総複雑度はO（log N）であることがわかります。
挿入
タスク ：ヒープに新しいアイテムを挿入します。
アルゴリズム ：1つの要素の束を作成し、その束と組み合わせます。
難易度 ：O（1）+ O（log（N））= O（log（N））
最低
タスク ：ヒープ上の最小値を見つけます。
アルゴリズム ：明らかに、最小値はルートリストにあります。つまり、それを見つけるにはルートリストを調べる必要があります。
難易度 ：O（
root_list.length
）= O（ログ（N））。
エキスミン
タスク ：最小要素を削除します。
アルゴリズム ：
Minimum
を使用して検索します。 ルートリストから削除します。 彼の子のインバーテッドリストから、新しいヒープ（H 1 ）のroot_listを作成し、元のヒープをH 1と結合します。
難易度 ：最小値を抽出する各操作はO（log N）で機能するため、O（log N）+ O（log N）+ O（log N）= O（log N）
減らす
タスク ：この頂点のデータ値を減らします。
アルゴリズム ：上部の値を減らします。 次に、ヒーププロパティがピークとその先祖に対して違反される可能性があります。その後、それらの場所を変更します。 ピークがその場所に「現れる」まで、このプロセスを続けます。 このアルゴリズムは、バイナリヒープのアルゴリズムと同じように機能します。
難易度 ：最悪の場合、頂点はルートにポップアップします。つまり、O（log N）アクションを実行します（各ステップの頂点は1レベル高くなり、二項ツリーの高さはT.5 O（log N）です）
削除する
タスク ：任意の要素を削除します。
アルゴリズム ：最初に、減少を使用して、頂点の値を可能な限り最小にします。 そして、ヒープの最小値（
ExtractMin
）を削除します。
難易度 ：O（log N）+ O（log N）= O（log N）
おわりに
二項ヒープのデータ構造を調べ、その漸近的な動作を証明しました。
次の記事では、二項ヒープに基づいて、やや複雑なデータ構造、つまりフィボナッチヒープを構築します。
rain.ifmo.ru/cat/view.php/vis/heaps/binomial-2001で二項ヒープをいじることができます。
T.Kormenの「アルゴリズム：構築と分析」で詳細を読むことができます。
ご清聴ありがとうございました。またお会いしましょう！