アルゴリズムとデータ構造編【データ構造】 第9章 ヒープ

先頭へ戻る

この章の概要

この章の概要です。

関連する話題が、以下のページにあります。

ヒープ

ヒープは、木構造の一種で、格納されている全ての要素の中から、最小値または最大値を持つ要素を探すことに適した構造です。

ヒープという言葉は、メモリ領域の一つを指して使うことがあります。本章のテーマは、それとは関係ありません。

ヒープは、根が最小値、または最大値となるように構成します。根が最小値とした場合、ある節の値は必ずその親以上の値になります二分探索木と違い、ある節が持っている子同士には、特に条件はありません

この条件を満たした木のイメージは、次のようになります。

ヒープ構造

ここでは二分木の形を取っていますが、子の数はいくつでも構いません。しかし、単にヒープといった場合は、子が2つずつの二分ヒープ(バイナリヒープ)のことを指す場合が多いです。


二分ヒープの実装

二分ヒープは、木構造の一種なので、第7章第8章で見たような、二分木や二分探索木と同じような方法で実装できます。しかし、実際にはこれらと同じ方法では実装しないのが一般的です。これは、もっと効率の良い方法があるからです。

次のようなヒープをイメージします。

ヒープ

○の中の数値は、格納されている値を示している訳ではなく、根から順番に連番を振っただけです。

この数値を観察すると、次のような法則があることが分かります。

そして、これらの法則を満たすための要件として、根の値が 0 ではなく 1 である必要があります

これらの法則は、木の形が完全二分木になっていなくても、常に要素を左側へ集めるように構成していけば満たし続けることができます。

ヒープ

要素が1つ欠けましたが、法則が崩れることはありません。

こういった法則があれば、木構造を配列で表現することが可能です。○の中の数値をそのまま、配列の添字に使えばいいのです。

では、実際にプログラムを作ってみます。

/* main.c */

#include <stdio.h>
#include <string.h>
#include "heap.h"


/* コマンド */
enum Cmd_tag {
    CMD_INSERT,
    CMD_REMOVE_ROOT,
    CMD_SEARCH,
    CMD_PRINT,
    CMD_EXIT,

    CMD_NUM
};

/* コマンド文字列の種類 */
enum CmdStr_tag {
    CMD_STR_SHORT,
    CMD_STR_LONG,

    CMD_STR_NUM
};

/* コマンドの戻り値 */
enum CmdRetValue_tag {
    CMD_RET_VALUE_CONTINUE,
    CMD_RET_VALUE_EXIT,
};

/* コマンド文字列 */
static const char* const CMD_STR[CMD_NUM][CMD_STR_NUM] = {
    { "i", "insert" },
    { "r", "remove_root" },
    { "s", "search" },
    { "p", "print" },
    { "e", "exit" }
};


static void create_heap(void);
static void delete_heap(void);
static void print_explain(void);
static void print_blank_lines(void);
static enum CmdRetValue_tag get_cmd(void);
static enum CmdRetValue_tag cmd_insert(void);
static enum CmdRetValue_tag cmd_remove_root(void);
static enum CmdRetValue_tag cmd_search(void);
static enum CmdRetValue_tag cmd_print(void);
static enum CmdRetValue_tag cmd_exit(void);
static int insert_elem(int value);
static int remove_root_elem(int* value);
static int search_elem(int value);
static void print_elem(void);
static void get_line(char* buf, size_t size);


/* コマンド実行関数 */
typedef enum CmdRetValue_tag (*cmd_func)(void);
static const cmd_func CMD_FUNC[CMD_NUM] = {
    cmd_insert,
    cmd_remove_root,
    cmd_search,
    cmd_print,
    cmd_exit
};


static Heap gHeap;


int main(void)
{
    create_heap();

    while( 1 ){
        print_explain();

        if( get_cmd() == CMD_RET_VALUE_EXIT ){
            break;
        }

        print_blank_lines();
    }

    delete_heap();

    return 0;
}

/* ヒープを作成 */
void create_heap(void)
{
    gHeap = heap_create( 4 );
}

/* ヒープを削除 */
void delete_heap(void)
{
    heap_delete( gHeap );
    gHeap = NULL;
}

/*
    説明文を出力
*/
void print_explain(void)
{
    puts( "コマンドを入力して下さい。" );
    printf( " ヒープに要素を挿入する: %s (%s)\n", CMD_STR[CMD_INSERT][CMD_STR_SHORT], CMD_STR[CMD_INSERT][CMD_STR_LONG] );
    printf( " ヒープから根を取り除く: %s (%s)\n", CMD_STR[CMD_REMOVE_ROOT][CMD_STR_SHORT], CMD_STR[CMD_REMOVE_ROOT][CMD_STR_LONG] );
    printf( " ヒープから要素を探す: %s (%s)\n", CMD_STR[CMD_SEARCH][CMD_STR_SHORT], CMD_STR[CMD_SEARCH][CMD_STR_LONG] );
    printf( " ヒープの内容を表示する: %s (%s)\n", CMD_STR[CMD_PRINT][CMD_STR_SHORT], CMD_STR[CMD_PRINT][CMD_STR_LONG] );
    printf( " 終了する: %s(%s)\n", CMD_STR[CMD_EXIT][CMD_STR_SHORT], CMD_STR[CMD_EXIT][CMD_STR_LONG] );
    puts( "" );
}

/*
    空白行を出力
*/
void print_blank_lines(void)
{
    puts( "" );
    puts( "" );
}

/*
    コマンドを受け付ける
*/
enum CmdRetValue_tag get_cmd(void)
{
    char buf[20];
    enum Cmd_tag cmd;
    int i;

    get_line( buf, sizeof(buf) );

    cmd = CMD_NUM;
    for( i = 0; i < CMD_NUM; ++i ){
        if( strcmp( buf, CMD_STR[i][CMD_STR_SHORT] ) == 0
         || strcmp( buf, CMD_STR[i][CMD_STR_LONG] ) == 0
        ){
            cmd = i;
            break;
        }
    }

    if( 0 <= cmd && cmd < CMD_NUM ){
        return CMD_FUNC[i]();
    }
    else{
        puts( "そのコマンドは存在しません。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    insertコマンドの実行
*/
enum CmdRetValue_tag cmd_insert(void)
{
    char buf[40];
    int value;

    puts( "ヒープに入れる数値データを入力して下さい。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );

    if( insert_elem( value ) ){
        printf( "%d を追加しました。\n", value );
    }
    else{
        printf( "%d の追加に失敗しました。\n", value );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    remove_rootコマンドの実行
*/
enum CmdRetValue_tag cmd_remove_root(void)
{
    int value;

    if( remove_root_elem(&value) ){
        printf( "%d を取り除きました。\n", value );
    }
    else{
        puts( "根を取り除くことに失敗しました。" );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    searchコマンドの実行
*/
enum CmdRetValue_tag cmd_search(void)
{
    char buf[40];
    int value;

    puts( "ヒープから探し出す数値データを入力して下さい。" );
    fgets( buf, sizeof(buf), stdin );
    sscanf( buf, "%d", &value );


    if( search_elem(value) ){
        printf( "%d が見つかりました。\n", value );
    }
    else{
        printf( "%d は見つかりませんでした。\n", value );
    }

    return CMD_RET_VALUE_CONTINUE;
}

/*
    printコマンドの実行
*/
enum CmdRetValue_tag cmd_print(void)
{
    print_elem();

    return CMD_RET_VALUE_CONTINUE;
}

/*
    exitコマンドの実行
*/
enum CmdRetValue_tag cmd_exit(void)
{
    puts( "終了します。" );

    return CMD_RET_VALUE_EXIT;
}

/*
    要素を入れる
*/
int insert_elem(int value)
{
    return heap_insert( gHeap, value );
}

/*
    要素を取り出す
*/
int remove_root_elem(int* value)
{
    return heap_remove_root( gHeap, value );
}

/*
    要素を探す
*/
int search_elem(int value)
{
    return heap_search(gHeap, value);
}

/*
    木の中身を出力
*/
void print_elem(void)
{
    heap_print( gHeap );
}

/*
    標準入力から1行分受け取る

    受け取った文字列の末尾には '\0' が付加される。
    そのため、実際に受け取ることができる最大文字数は size - 1 文字。

    引数:
        buf:    受け取りバッファ
        size:   buf の要素数
    戻り値:
        buf が返される
*/
void get_line(char* buf, size_t size)
{
    fgets(buf, size, stdin);

    /* 末尾に改行文字があれば削除する */
    char* p = strchr(buf, '\n');
    if (p != NULL) {
        *p = '\0';
    }
}
/* heap.c */

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "heap.h"


/* ヒープ */
struct Heap_tag {
    int*   data;        /* データ本体 */
    int    capacity;    /* 最大容量 */
    int    first_empty; /* 空になっている最初の位置 */
};

#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

static void up_heap(Heap heap, int index);
static void down_root(Heap heap);
static void heap_print_node(const Heap heap, int index, int level);


/* ヒープを作る */
Heap heap_create(int capacity)
{
    struct Heap_tag* heap = malloc( sizeof(struct Heap_tag) );
    heap->data = malloc( sizeof(int) * (capacity + 1) );  /* 添字を 1 から始めるため、+ 1 して確保 */
    heap->capacity = capacity;
    heap->first_empty = 1;  /* 0番目は使わない */

    return heap;
}

/* ヒープを削除する */
void heap_delete(Heap heap)
{
    if( heap != NULL ){
        free( heap->data );
        free( heap );
    }
}

/* ヒープに要素を追加する */
int heap_insert(Heap heap, int value)
{
    int index;

    /* 容量が一杯でないか確認 */
    if( heap->capacity < heap->first_empty ){
        return 0;
    }


    /* まず、末尾に追加する */
    index = heap->first_empty;
    heap->data[index] = value;
    heap->first_empty += 1;

    /* 適切な位置まで浮かび上がらせる */
    up_heap(heap, index);

    return 1;
}

/* ヒープから根を取り除く */
int heap_remove_root(Heap heap, int* value)
{
    /* ヒープが空でないか確認する */
    if( heap_getsize(heap) <= 0 ){
        return 0;
    }


    *value = heap->data[1];

    /* ヒープの最後にある要素を、先頭に移動する */
    heap->first_empty -= 1;
    heap->data[1] = heap->data[heap->first_empty];

    /* 先頭に移動させた要素を、正しい位置に沈める */
    down_root(heap);

    return 1;
}

/* ヒープから要素を探す */
int heap_search(const Heap heap, int value)
{
    int i;

    for( i = 1; i < heap->first_empty; ++i ){
        if( heap->data[i] == value ){
            return 1;
        }
    }

    return 0;
}

/* ヒープに格納されている要素数を返す */
int heap_getsize(const Heap heap)
{
    return heap->first_empty - 1;
}

/* ヒープの内容を出力する */
void heap_print(const Heap heap)
{
    if( heap == NULL || heap_getsize(heap) <= 0 ){
        return;
    }

    heap_print_node( heap, 1, 0 );
}

/* ヒープの指定要素を適切な位置まで浮かび上がらせる */
void up_heap(Heap heap, int index)
{
    while( index > 1 ){  /* 根に到達したら終わり */
        int parent = index / 2;

        if( heap->data[parent] > heap->data[index] ){
            /* 親との大小関係が逆なら入れ替える */
            SWAP( int, heap->data[parent], heap->data[index] );
            
            /* さらに親を辿る */
            index = parent;
        }
        else{
            /* 大小関係が正常だったら終わり */
            break;
        }
    }
}

/* 根を適切な位置まで沈める */
void down_root(Heap heap)
{
    int index = 1;  /* 根から開始 */

    while( index * 2 <= heap->first_empty ){
        int child = index * 2;  /* 左の子の位置 */

        /* 2つの子があるなら、小さい方を使う */
        /* 右の子の添字は、左の子の添字 + 1 である */
        if( child + 1 < heap->first_empty ){
            if( heap->data[child] > heap->data[child + 1] ){
                child = child + 1;
            }
        }

        /* 子との大小関係が逆なら、入れ替える */
        if( heap->data[child] < heap->data[index] ){
            SWAP( int, heap->data[child], heap->data[index] );
            index = child;
        }
        else {
            break;
        }
    }
}

/* ヒープの内容を出力する */
void heap_print_node(const Heap heap, int index, int level)
{
    int i;

    for( i = 1; i < level; ++i ){
        printf( "    " );
    }
    if( level > 0 ){
        printf( "+---" );
    }
    printf( "%d\n", heap->data[index] );


    /* 左の子 */
    index *= 2;
    if( index < heap->first_empty ){
        heap_print_node( heap, index, level + 1 );
    }

    /* 右の子 */
    index += 1;
    if( index < heap->first_empty ){
        heap_print_node( heap, index, level + 1 );
    }
}
/* heap.h */

#ifndef HEAP_TREE_H
#define HEAP_TREE_H


/* ヒープ型 */
typedef struct Heap_tag* Heap;


/*
    ヒープを作る

    引数:
        capacity:	ヒープの最大容量。

    戻り値:
        作成されたヒープ。
        使い終わったら、heap_delete関数に渡して削除する。
*/
Heap heap_create(int capacity);

/*
    ヒープを削除する

    引数:
        heap:	ヒープ
*/
void heap_delete(Heap heap);

/*
    ヒープに要素を挿入する

    引数:
        heap:	ヒープへのポインタ
        value:	挿入する要素の値
    戻り値:
        成功したら 0以外、失敗したら 0 を返す。
*/
int heap_insert(Heap heap, int value);

/*
    ヒープから根を取り除く

    引数:
        heap:	ヒープへのポインタ
        value:	取り除かれた要素を受け取るメモリアドレス
    戻り値:
        成功したら 0以外、失敗したら 0 を返す。
*/
int heap_remove_root(Heap heap, int* value);

/*
    ヒープから要素を探す

    引数:
        heap:	ヒープ
        value:	探し出す要素の値
    戻り値:
        要素が見つかれば 0以外、見付からなければ 0 を返す。
*/
int heap_search(const Heap heap, int value);

/*
    ヒープに格納されている要素数を返す

    引数:
        heap:	ヒープ
    戻り値:
        格納されている要素の個数。
*/
int heap_getsize(const Heap heap);

/*
    ヒープの内容を出力する

    引数:
        heap:	ヒープ
*/
void heap_print(const Heap heap);


#endif

初期化

これまでの解説通り、ヒープは配列として実装できます。ここで、根の添字が 1 になるように実装すると、全体的にコードを簡潔に記述できます。そのため、添字 0 のところは未使用なままにしてあります。

0番目の要素には、ヒープ内の要素数を入れておくなどして、使いまわすこともできます。

要素の挿入

要素の挿入は、heap_insert関数で実装しています。

まずヒープの末尾に入れてから、適切な位置まで移動させることで実現します。ヒープの末尾をいちいち探していたら効率が悪いので、追加できる場所を常に first_empty という変数に保存してあります。

適切な位置へ移動させる処理は、up_heap関数にあります。この処理は、自分の値と、自分の親の値を比較して、大小関係が逆転していたら、入れ替えること繰り返せば実現できます。このとき、自分の親は、「自分の添字 / 2」の位置にあることを思い出して下さい。根まで到達するか、自分の値と自分の親の値の大小関係が正しい地点まで来たら完了です。

根を取り除く

根を取り除く処理は、heap_remove_root関数にあります。この処理は、まず、ヒープの末尾にある要素を根の位置に上書きすることから始まります。根を取り除きたいのですから、何も気にせず根を上書きして構いません。

続いて、根に上書きした値を、適切な位置に移動させていきます。この処理は、down_root関数にあります。

up_heap関数とは逆で、自分の値と、2つの子の値とを比較して、大小関係が逆転していたら入れ替えます。このとき、子が1つしか無い可能性を考慮することを忘れてはいけません。また、子が2つある場合には、小さい方(根が一番大きくなる実装の場合は大きい方)の子と入れ替えるようにします。そうしないと最終的な結果が、根が一番小さく(または大きく)なりません。

まとめ

ヒープは木構造の一種で、根に最大値または最小値が来るように構成することで、最大値や最小値を効率よく取得できます。逆に、それ以外の要素を探索することには向いておらず、通常こういった操作は実装しません

要素の挿入、根の削除に要する計算量はいずれも O(log n) です

配列で表現できることが特徴的で、簡単な添字計算だけで親子を参照できます。余計な付加情報を持つ必要がない(例えば、他の要素を辿るためのポインタ等)ため、メモリ効率の面でも優れています。

最大値や最小値を効率的に取得できることから、ソートアルゴリズムに利用されることがあり、これをヒープソートと呼びます(【整列】第8章参照)。

また、登録される要素に何らかの優先度を設け、追加順序ではなく優先度の高い順番に取り出されるキュー(待ち行列)を実装することにも利用できます。このようなキューを、優先度付きキューと呼びます。優先度付きキューについては、次章で取り上げます。


練習問題

問題① この章のサンプル実装において、ヒープ内で最も大きい値を保持している要素を探す関数を作成して下さい。


解答ページはこちら


参考リンク



更新履歴

'2018/4/3 サンプルプログラム内の up_heap関数の実装を修正。 常に根に至るまで繰り返す実装になっていた。非効率であり、解説内容とも一致していなかった。

'2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

'2018/2/12 サンプルプログラムの改善(fgets が受け取った改行文字の削除の方法を修正。const、static の付加)

'2017/11/13 サンプルプログラムで、存在しないコマンドが入力されたときに、未初期化の変数を参照していたのを修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

≪更に古い更新履歴を展開する≫



前の章へ(第8章 二分探索木)

次の章へ(第10章 優先度付きキュー)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS