二項ヒープの構造
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/05 08:19 UTC 版)
二項ヒープは、以下の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つの二項木から構成される（下図参照）。
※この「二項ヒープの構造」の解説は、「二項ヒープ」の解説の一部です。
「二項ヒープの構造」を含む「二項ヒープ」の記事については、「二項ヒープ」の概要を参照ください。
ウィキペディア小見出し辞書の「二項ヒープの構造」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 二項ヒープの構造のページへのリンク
