先頭へ戻る

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

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

先頭へ戻る

問題①

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


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

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

ヒープ
ヒープ

葉にあたるのは、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 管理者情報 プライバシーポリシー