先頭へ戻る

ヒープ 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【データ構造】 第9章

Programming Place Plus トップページ -- アルゴリズムとデータ構造編

先頭へ戻る

問題①

問題① ヒープの実装に用いる配列の 0番目の要素は空いています。ここに、ヒープに含まれている要素の個数を入れて管理するようにしてください。


配列の要素の型が整数型でなければなりませんが、小さな無駄が消えます。

heap.c だけを変更すれば実現できます。

// heap.c

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


// ヒープ
struct Heap_tag {
    int*      data;        // データ本体
    size_t    capacity;    // 最大容量
};

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

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


/*
    ヒープを作る
*/
Heap heap_create(size_t capacity)
{
    struct Heap_tag* heap = malloc( sizeof(struct Heap_tag) );
    heap->data = malloc( sizeof(int) * (capacity + 1) );  // 添字を 1 から始めるため、+ 1 して確保
    heap->capacity = capacity;

    heap->data[0] = 0;  // 要素数

    return heap;
}

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

/*
    ヒープに要素を追加する
*/
bool heap_insert(Heap heap, int value)
{
    size_t size = heap_getsize(heap);

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


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

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

    return true;
}

/*
    ヒープから根を取り除く
*/
bool heap_remove_root(Heap heap, int* value)
{
    size_t size = heap_getsize(heap);

    // ヒープが空でないか確認する
    if( size <= 0 ){
        return false;
    }


    *value = heap->data[1];

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

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

    return true;
}

/*
    ヒープから要素を探す
*/
bool heap_search(const Heap heap, int value)
{
    size_t size = heap_getsize(heap);

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

    return false;
}

/*
    ヒープに格納されている要素数を返す
*/
size_t heap_getsize(const Heap heap)
{
    return heap->data[0];
}

/*
    ヒープの内容を出力する
*/
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, size_t index)
{
    while( index > 1 ){  // 根に到達したら終わり
        size_t 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)
{
    size_t size = heap_getsize(heap);
    int index = 1;  // 根から開始

    while( index * 2 <= size + 1 ){
        int child = index * 2;  // 左の子の位置

        // 2つの子があるなら、小さい方を使う
        // 右の子の添字は、左の子の添字 + 1 である
        if( child + 1 < size + 1 ){
            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, size_t index, int level)
{
    size_t size = heap_getsize(heap);

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


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

    // 右の子
    index += 1;
    if( index < size + 1 ){
        heap_print_node( heap, index, level + 1 );
    }
}

要素数が heap->data[0] で管理されています。代わりに、first_empty メンバは削除しました。

なお、heap->data[0] に要素数が入っていることは少々不明確ではありますから、インライン関数(C言語編第57章)を経由させるなどすると分かりやすくなるかもしれません。

問題②

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


この問題は、ヒープの実装をよく検討することから始めましょう。

まず、サンプル実装は、最も小さい値が根に来るようにしています。また、要素を追加する際には、まず末尾に置いてから、適切な位置まで浮かび上がらせるように実装されています。そのため、最も大きい値は必ず、葉にあたる部分にあるはずです。ここで、本編の図をあらためて確認してみましょう。

ヒープ
ヒープ

葉にあたるのは、4・5・6であり、この中で最も大きい値を持つ要素が探せればよい訳です。問題はどうやって、ある要素が葉なのか、そうでないのかを知るかです。

子の添字は「左の子は、親の添字 * 2」「右の子は、親の添字 * 2 + 1」ですから、自分の添字を2倍した結果が、ヒープ全体の要素数を越えてしまう場合は、その要素は葉であることが分かります。

この考え方で探索することは可能ですが、これだと無意味なのです。なぜなら、結局すべての要素を調査することになってしまうので、それなら始めから、要素の値を見て最大値を探せばいいからです。

もう少しまともにするには、ヒープを構成する配列のどの部分からが葉を表しているのかを考えることです。そこで、葉ではない最後の要素を考えます。

葉ではないということは、子を持っているということです。そこで、子の側から考えてみると、ヒープの末尾の要素(これは必ず葉です)の親が、最後の「葉でない要素」だと分かります。

ヒープの末尾の要素は、要素数さえ管理できていればすぐに分かります(サンプル実装では heap_getsize関数が返す値が要素数です)から、最後の親の添字は、「heap_getsize() / 2」で求められます。従って、最初の葉の添字は、「heap_getsize() / 2 + 1」です。

最初の葉の添字が分かれば、そこから末尾までの要素を調べて、最大の値を探すだけです。この関数は、次のように書けます。

int heap_max_value(const Heap heap)
{
    int max = INT_MIN;

    for( int i = heap_getsize(heap) / 2 + 1; i < heap->first_empty; ++i ){
        if( max < heap->data[i] ){
            max = heap->data[i];
        }
    }
    return max;
}


参考リンク


更新履歴

'2014/12/14 第10章で優先度付きキューを扱うことにしたので、問題を変更した。

'2013/2/2 新規作成。



第9章のメインページへ

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー