MeldablePriorityQueuesとSkewHeaps

メルダブル優先キュー

定義

ランダム化されたメルダブルヒープ（メルダブルヒープまたはランダム化されたメルダブル優先度キュー）は、基になる構造もヒープ順に並べられたバイナリツリーである優先度キューベースのデータ構造として定義されます。ただし、基礎となる二分木の形に厳格な規則はありません。

利点

• このアプローチには多くの機能があります。つまり、同様のデータ構造に勝る利点があります。
• 他のデータ構造よりもシンプルなアプローチを提供します。
• ランダム化されたメルダブルヒープのすべての操作は簡単に適用でき、複雑さの範囲内の定数係数は小さくなります。
• バランス状態を維持する必要もありません。また、ノード内の衛星情報も必要ありません。
• 最後に、この構造は最悪の場合の時間効率が良好です。ほとんどの場合、個々の操作の実行時間は対数であり、確率が高くなります。

スキューヒープ

スキューヒープ（または自己調整ヒープ）は、バイナリツリーとして実装されたヒープデータ構造として定義されます。

スキューヒープは、バイナリヒープよりも迅速にマージできるため、有利です。

バイナリヒープとは異なり、構造上の制約がないため、ツリーの高さが対数であるという保証はありません。

2つの条件のみが満たされる必要があります-

• 一般的なヒープの順序はそこで維持する必要がありますが（ルートは最小で、サブツリーでも同じことが再帰的に当てはまります）、バランスの取れたプロパティ（最後を除くすべてのレベルがいっぱいである必要があります）は必要ありません。
• スキューヒープの主な操作はマージのみです。マージのみに関連するinsert、extractMin（）などの他の操作を実装できます。

例

スキューヒープ1を

想定される2番目のヒープ

そして、最終的なマージされたツリーを

再帰的マージプロセス

merge(a1, a2)
Let a1 and a2 be the two min skew heaps to be merged. Let a1’s root be smaller than a2’s root (If not smaller, we can swap to get the same).
We swap a1->left and a1->right.
a1->left = merge(a2, a1->left)