二項ヒープ
ヒープからある要素を削除するには、そのキー値を負の無限大へ減算し(あるいは、ヒープ内の任意の要素よりも小さい値へ減算し)、ヒープ内の最小値を削除する。
ヒープの最小要素を見つけるには、ただ二項木たちの根の中で最小のものを見つけるだけでよい。この処理は O(log n)時間内にたやすく完了できる。
最小要素を含む二項木を指すポインタを使うことによって、この操作にかかる時間をO(1)にまで減らすことができる。そのポインタは最小要素検索以外の任意の操作を行うときにおいても必ず更新しなければならない。この操作は、任意の操作を行う時間とは別にO(log n)時間内に完了する。
二項ヒープは、以下の2つの性質を満たす二項木の組で実装される。
ヒープ内のそれぞれの二項木は、「ノードのキーはその親のキーよりも大きいか等しい」という最小ヒープの特性に従う。
二項木は次数 0を含む各々の次数について、ただ1つ存在、あるいは存在しないかのいずれかである。
第1の特徴は、それぞれの二項木の根は、1つの木の中に最小のキーを持つことを保証している。これはヒープ全体に当てはまる。 第2の特徴は、n個の要素を持つ二項ヒープは高々 log(n + 1) の二項ヒープから構成されていることを意味する。実際、これらの木の数字と順番はn要素の数字によって一意に決定される。それぞれの二項木はnの2進表現の1に一致する。例えば、13という数は2進数では「1101」であり、 2 3 + 2 2 + 2 0 {\displaystyle 2^{3}+2^{2}+2^{0}} と表現される。つまり、13個の要素を持つ二項ヒープは次数 3、2、0の3つの二項木から構成される(下図参照)。