ヒープとは―データ構造の1つ。ヒープ領域とはメモリ領域のこと。

データ構造やヒープ領域とは何かなど、ヒープをテーマに情報をまとめています。

▲記事トップへ

目次

この記事の目次です。

1. ヒープとは
2. データ構造としてのヒープとは
3. メモリ領域としてのヒープ領域とは

更新履歴

1. ヒープとは

ヒープとは、英語でheapと記述する言葉で、IT用語では、データ構造、またはメモリ領域のことを表す言葉です。

英語でheapと記述

ヒープは、英語でheapと記述される用語です。

heapの意味

一般的な英語辞典のheapの意味は以下になります。

1. 積み重なったもの、堆積
2. 群れ、たくさん、幾度も、何度も
3. ぽんこつ、がたのきたもの

heap data structure（データ構造のヒープ）

一般的な英語辞典にはありませんが、heap data structure（データ構造のヒープ）もヒープといいます。

heap area（ヒープ領域）

同じく一般的な英語辞典にはありませんが、コンピュータのメモリ領域のheap area（ヒープ領域）もヒープといいます。

あと、heap memory（ヒープメモリ）もヒープといいます。

2. データ構造としてのヒープとは

データ構造としてのヒープとは、配列を使って半順序木を実現したデータ構造のことをいいます。

データ構造とは

データ構造とは、データが相互に関連づけられた構造を形作ったもののことをいいます。 データ構造は、基本データ構造と問題向きデータ構造に分類されます。

基本データ構造は、基本データ型、構造型などが分類され、問題向きデータ構造には、連結リスト、木、スタック、キューなどが分類されます。

配列とは

配列とは、同じデータ型のデータが集まることによって実現されるデータ構造のことをいいます。

データ型とは、データの種類のことで、たとえば、「-1、0、1、2、3・・・」は整数型、「true、false」は論理型です。

半順序木とは

半順序木とは、すべての節について親の値が子の値よりも小さいか等しいという条件の2分木です。 ①完全2分木、②親の値 ≦ 子の値、③兄弟間に大小の制約が無い、という条件の木です。

ただし、②の条件は「親の値 ≧ 子の値」と親子の関係を逆転させる場合もあります。

ヒープのデータ構造イメージ

ヒープのデータ構造のイメージです。

ヒープソート

ヒープソートは、木構造を配列で表現するデータ構造を利用したソートアルゴリズムです。 利用する木構造は半順序木とよばれる順序木を使用します。 未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移し、この操作を繰り返して、未整列の部分を縮めていきます。

3. メモリ領域としてのヒープ領域とは

メモリ領域としてのヒープとは、動的変数で利用されるメモリ領域である、ヒープ領域のことをいいます。

メモリ領域とは

メモリ領域とは、コンピュータで記憶媒体に保存されたプログラムを実行する際に、プログラムをロードする主記憶の記憶領域ことをいいます。

主記憶とは

主記憶とは、CPUなどのプロセッサーが直接アクセスすることのできる記憶装置のことをいいます。

1次記憶装置、メインメモリともいわれますが、単にメモリと言われることもあります。

変数とは

変数とは、データに固有の名前を付けて記憶して必要なときに利用できるようにしたもので、静的変数と動的変数があります。

静的変数は、プログラム実行前に記憶領域に割り付けられ、プログラムの実行中は、領域は解放されない変数。 動的変数は、プログラムの実行中に記憶領域に割り付けられ、ヒープ領域に割り付けられることが多い変数です。

ヒープ領域とは

ヒープ領域とは、プログラミングで動的に確保可能なメモリの領域のことをいいます。

C言語のヒープ領域にメモリを確保する例

C言語ではmalloc関数の呼出しでヒープ領域のメモリが確保され、free関数で解放されます。 なお、ヒープ領域の構造は設計によるようでデータ構造のヒープが必ずしも使用されるわけではないようです。

malloc関数

mallocは動的にメモリを確保します。

#include <stdlib.h>
/* ヒープ上にsizeバイトの領域を確保 */
void *malloc(size_t size);

mallocは、大きさsizeバイトのメモリ領域をヒープ上に確保し、そのメモリ領域の先頭のポインタをを返します。 メモリ領域が確保できないときはNULLを返します。

サンプルプログラム

C言語のヒープ領域にメモリを確保するサンプルプログラムとコンパイルから実行までの手順です。 コンパイルはgccコンパイラーを使用しています。

ソースコード

//ファイル名：malloc.c

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
	int *p = malloc(sizeof(int)); /*メモリ領域の確保*/
	if(p==NULL){
     	/*メモリ確保に失敗*/
     	printf("メモリ確保に失敗しました。\n");
		return 1;
	}
	*p = 999;
	printf("アドレス(%p)の変数の値は、%dである。\n", p,*p);
	free(p);	/* mallocで確保したメモリ領域を開放 */
	return 0;
}

コンパイル

$gcc -o malloc malloc.c

実行

作成したmallocというファイルと同じディレクトリで./mallocとコマンドラインに入力して、 「アドレス(16進数の数字)の変数の値は、999である。」と出力されればOKです。

例）
$./malloc
アドレス(0x8739008)の変数の値は、999である。

更新履歴

このページの更新履歴です。

• 2022/1/31 C言語のヒープ領域にメモリを確保する例を追記しました。
• 2021/11/24 ヒープソートについて追記しました。
• 2016/12/26 記事をUPしました。

戻る