木きとヒープの基本きほん

導入どうにゅう

この講義こうぎで最重要さいじゅうようなのは、木きは「親子関係おやこかんけいで要素ようそを整理せいりする構造こうぞう」であり、ヒープはその上うえに「親おやと子この大小関係だいしょうかんけい」を課かしたものだということです。

配列はいれつは横よこに並ならべる構造こうぞうですが、木きは分岐ぶんきしながら下したへ広ひろがります。この見方みかたが分わかると、優先度ゆうせんどつきキューや探索木たんさくぎの話はなしへ自然しぜんに進すすめます。

用語ようごと定義ていぎ

木きTree とは、根ねから枝分えだわかれする階層構造かいそうこうぞうです。

ヒープHeap とは、完全二分木かんぜんにぶんぎの形かたちをもち、親おやと子この間あいだに大小関係だいしょうかんけいをもつ構造こうぞうです。

優先度ゆうせんどつきキューPriority queue とは、最もっとも優先度ゆうせんどの高たかい要素ようそから取とり出だす構造こうぞうです。

方針ほうしん

まず木きを「親おやと子こ」で読よむ構造こうぞうとして捉とらえます。そのうえで、ヒープでは「親おやが子こより大おおきい」または「小ちいさい」という条件じょうけんを加くわえると、最小値さいしょうちや最大値さいだいちを取とり出だしやすくなることを見みます。

直感的ちょっかんてきな説明せつめい

教室きょうしつの席順せきじゅんのように横よこに並ならんだ構造こうぞうでは、中央ちゅうおうの近ちかくも端はしも同おなじように 1 列れつの中なかにあります。いっぽう組織図そしきずのような構造こうぞうでは、「だれの下したにだれがいるか」が重要じゅうようです。木きはこのような階層かいそうを表あらわすのに向むいています。

厳密げんみつな説明せつめい

見分みわけ方かた

• 親子関係おやこかんけいや階層かいそうを使つかって整理せいりしたいなら、木きを疑うたがいます。
• 最小値さいしょうちや最大値さいだいちを繰くり返かえし取とり出だしたいなら、ヒープが候補こうほです。
• 完全かんぜんに整列せいれつされた順序じゅんじょが必要ひつようなら、ヒープだけでは足たりないことに注意ちゅういします。

最終形さいしゅうけい

一言ひとことでいうと

• 木きは階層かいそうを表あらわす構造こうぞうで、ヒープはそこに優先順位ゆうせんじゅんいを扱あつかいやすい規則きそくを加くわえたものです。