二項ヒープ 二項ヒープの構造

ウィキペディア

二項ヒープ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/04/12 04:52 UTC 版)

二項ヒープの構造

二項ヒープは、以下の2つの性質を満たす二項木の組で実装される。

• ヒープ内のそれぞれの二項木は、「ノードのキーはその親のキーよりも大きいか等しい」という最小ヒープの特性に従う。
• 二項木は次数 0を含む各々の次数について、ただ1つ存在、あるいは存在しないかのいずれかである。

第1の特徴は、それぞれの二項木の根は、1つの木の中に最小のキーを持つことを保証している。これはヒープ全体に当てはまる。 第2の特徴は、n個の要素を持つ二項ヒープは高々 log(n + 1) の二項ヒープから構成されていることを意味する。実際、これらの木の数字と順番はn要素の数字によって一意に決定される。それぞれの二項木はnの2進表現の1に一致する。例えば、13という数は2進数では「1101」であり、$2^{3}+2^{2}+2^{0}$

key 1, 2, …, 13の要素を含む二項木の例。このヒープは次数 0, 2, 3の3つの二項木から構成されている。