- CMS比較.com >
- インターネット用語辞典【ヒープとは？】
ヒープとは？
▼ヒープ▼
ヒープ
C言語などにおける動的に確保できる記憶装置 メモリ領域としての「ヒープ領域」については、リンク先を参照。
木構造 (データ構造) 木構造の一つ。下記参照。
ヒープ（Heap）は、木構造 (データ構造) 木構造の一つ。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多い。
親要素が常に2つの子要素より大きくならない(またはその逆)構造になっている。
挿入、削除がO(log n)で可能。探索はO(n)。
ルートが常に最小(最大)要素となっているので、ルートの削除を繰り返すことで、ソートを行うことができる。
このときの計算量はO(nlogn)。(ヒープソート)
ヒープは木構造の一種であり、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ。子要素が複数ある場合、子要素間の大小関係に制約はない。
【情報源】Wikipedia
【引用元URL】http://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97
▼ヒープソート▼
ヒープソートとはリストの並べ替えをヒープ構造を用いて行うソートアルゴリズムの一つである。
アルゴリズムは、以下のように 2 つのフェーズで構成される。
未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。
ルート（最大値または最小値）を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。
計算量は O(n \log n) となる。安定ソート ではない。
ヒープ構造は、ポインタ等の制御用データが不要で、データ自体の 配列 だけで表現できるという利点がある。ヒープソートを実装する際には、この利点を使い、元データの配列として確保された領域をヒープ構造や整列済みリストに転用していく。
【情報源】Wikipedia
【引用元URL】http://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97
▼ヒープ領域▼
ヒープ領域（ヒープりょういき）とはC言語などにおいて、動的に確保可能なメモリの領域。ヒープ (heap) とは、『山積み』という言葉の中の『山』をさす英単語である。
データ構造のヒープとは直接的な関係が無い。
ヒープ領域は、2種類のラベルを持つ双方向線形リスト リストによって構成されている。初期状態では、リストはひとつの「未使用」ノードが全体を占めていて、メモリ確保関数(C言語:malloc,C++言語:new等)によって、「未使用」ノードから必要な分を切り取って「使用中」ノードと「未使用」ノードに分ける。確保したメモリが不要になった場合には、メモリ開放関数(C言語:free,C++言語:delete等)によってノードのラベルを「未使用」に書き換える。開放のつど、あるいはカウンタによって一定水準に達した時、連続した個々の「未使用」ノードが結合され、大きな「未使用」ノードに還元される。「未使用」ノードが不足した場合には、オペレーティングシステムに領域拡大を要求し、ヒープ領域が拡大される。「未使用ノード」と「使用中」ノードが混在し、ヒープ領域がバラバラに分断された状態をフラグメンテーション状態と呼ぶ。
【情報源】Wikipedia
【引用元URL】http://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97
▼「ヒープ」以外の用語▼
