Definição e significado de ビープ

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ビーフ

1. 牛肉のこと。
2. 中傷合戦のこと。ヒップホップなどの歌詞で見られる。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ヒープ

1. C言語などにおける動的に確保できるメモリ領域としての「ヒープ領域」については、リンク先を参照。
2. 木構造の一つ。下記参照。

ヒープ（Heap）は、木構造の一つ。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多いため、そちらを参照すること。

親要素が常に2つの子要素より大きくならない（またはその逆）構造になっている。挿入、削除がO(log n)で可能。探索はO(n)。ルートが常に最小（または最大）要素となっているので、ルートの削除を繰り返すことで、ソートを行うことができる。このときの計算量はO(n log n)。(ヒープソート)

構造

ヒープは最小値（または最大値）を求めるのに適した木構造の一種であり、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ。子要素が複数ある場合、子要素間の大小関係に制約はない。

実際には、木の高さの低い方（または深さの浅い方）から、また同じ高さでも左または右のどちらかに要素を寄せた木構造を作る。深さ n の要素がすべて使われるまで、深さ n + 1 の要素は作成しない。二分ヒープの場合、要素の添字を 1 から開始すると、要素 n の親は n / 2、子は 2n および 2n + 1 となる（添字を 0 から開始すると親は (n - 1) / 2、子は 2n + 1 と 2n + 2 である）。

後述する手順に従って操作すれば、データの出現順序に関わらず、このような構造を容易に維持できることがヒープの利点である。

実装

構造の節で述べたように、任意の要素に対する親要素と子要素は添字の計算で特定することができる。また要素が存在するか否かは、全要素数と比較することで判断できる。このためポインタ に相当するデータを持たなくても、データ自体を格納した配列だけでヒープ構造を実装することが可能である。

ただし個々の要素のデータ容量が大きい場合は、要素の入れ替えにおけるコピー処理の負荷が問題になる場合もある。対策として、敢えて各要素へのポインタ（あるいは各要素の添字）からなる配列を別に作成して、この配列でヒープ構造を実装するという選択も考えられる。

操作

探索

ヒープ構造では子要素間の大小関係に制約がないため、目的とする要素が見つかるまで全要素を順に調べる必要がある。したがって、任意のデータを探索する必要がある場合にヒープ構造を使うことは勧められない。

ただし、ルートに最小（または最大）の要素が来ることは保証されている。これを利用してソートを行うアルゴリズムがヒープソートである。

挿入

子は親より大きいか等しく、添字は 1 から開始するものとして記述する。また、木全体の要素数を N とする。

1. 操作対象の要素 n = N + 1 とし、追加する要素を n に置く。
2. 要素 n を親（n / 2）と比較する。要素 n がルート（n = 1）か、または比較結果が親以上なら終了。
3. 親の方が大きければ親子を入れ替え、n = n / 2 として繰り返す。

削除

子は親より大きいか等しく、添字は 1 から開始するものとして記述する。また、木全体の要素数を N とする。ルートを削除する手順は以下のとおりである。

1. 操作対象の要素 n = 1 とし、要素 N を 1（ルート）に移動する。
2. 要素 n を子（2n および 2n + 1）と比較する。子が存在しない（2n > N）か、またはすべての子の比較結果が要素 n 以上なら終了。
3. 小さいほうの子と要素 n を入れ替え、n を入れ替えた子の添字として繰り返す。

ルート以外を削除する場合も、要素 N を削除箇所に移動するところまでは同じである。ただし、その後の操作は以下の条件分岐が必要になる。

要素 N > 子要素の場合 

ルートの削除と同様に、葉に向かって入れ替え操作を繰り返す

要素 N < 親要素の場合 

挿入時と同様に、ルートに向かって入れ替え操作を繰り返す

なお削除前に正しいヒープ構造になっていれば、親要素 ≤ 子要素なので、両方が同時に成り立つことはない。

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ヒーブ（HEIB、Home economists in businessの略）は大学で家政学（生活科学）を修めて、企業の中で生活者としての女性の視点を尊重しつつ、家政学の専門知識を生かして、商品開発や消費者サービス、あるいは販売の現場で専門知識の提供をしながら、購入のアドヴァイスをする女性たちのことをいう。「企業内家政学士」と訳す場合もある。

大手のメーカーの中には商品開発の部門の中に「ヒーブ室」、もしくはそれに類した名所のセクションを設置しているところもある。たとえば、ハウス食品など。

関連項目

• 暮らし
• 生活
• 家政学

外部リンク

• 日本ヒーブ協議会