二項ヒープ
二項ヒープは二項木の集合として実装される(二分ヒープと比較すると、二分ヒープは単一の二分木から構成される)。二項木は再帰的に定義される。
次数 0の二項木は1つのノードをもつ。
次数 k の二項木は一つの根(root)をもち、その子はそれぞれ次数 k-1, k-2, ..., 2, 1, 0の二項木の親である。
次数 k の二項木は 2 k {\displaystyle 2^{k}} のノードを持ち、高さはk である。
その構造の特有さから、マージ操作は簡単に行うことができる。 例えば、次数 k の二項木を作るには、次のようにする。
次数 k-1の2つの木 T a {\displaystyle T_{a}} と T b {\displaystyle T_{b}} があるとする。
T a {\displaystyle T_{a}} (または T b {\displaystyle T_{b}} ) の一番左の子として、 T b {\displaystyle T_{b}} (または T a {\displaystyle T_{a}} )を付け加える。
この特徴は二項ヒープのマージ操作の中核を成すものであり、従来のヒープに優る大きな利点となっている。