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

1導入どうにゅう

この講義こうぎでは、根付ねつき木ぎの親子関係おやこかんけいと深ふかさを定義ていぎし、二分にぶんヒープの不変条件ふへんじょうけん、基本操作きほんそうさ、計算量けいさんりょうを説明せつめいする。

2根付ねつき木ぎ

木きは、任意にんいの二頂点間にちょうてんかんに道みちがただ一ひとつ存在そんざいする無向むこうグラフである。根付ねつき木ぎは、木きの一頂点いちちょうてんを根ねrootとして指定していした構造こうぞうである。根ねでない頂点ちょうてん $$v$$v について、$$v$$v から根ねへの道みちで $$v$$v の直後ちょくごにある頂点ちょうてんを $$v$$v の親おやparentという。親おやが $$v$$v である頂点ちょうてんを $$v$$v の子こchildという。根ねに親おやは存在そんざいしない。

頂点ちょうてん $$v$$v の深ふかさdepthは、根ねから $$v$$v への道みちの辺数へんすうである。根ねの深ふかさは $$0$$0 であり、子この深ふかさは親おやの深ふかさより $$1$$1 大おおきい。木きの高たかさheightは頂点ちょうてんの深ふかさの最大値さいだいちである。各頂点かくちょうてんの子こが高々たかだか $$2$$2 個こである根付ねつき木ぎを二分木にぶんぎbinary treeという。

3二分にぶんヒープ

$$n$$n 個この要素ようそをもつ完全二分木かんぜんにぶんぎcomplete binary treeは、最下段さいかだんを除のぞく各段かくだんが充足じゅうそくされ、最下段さいかだんの頂点ちょうてんが左ひだりから連続れんぞくしている二分木にぶんぎである。この形状けいじょうの高たかさは $$\lfloor {\log }_{2}n\rfloor$$\lfloor\log_2 n\rfloor（$$n>0$$n>0）であり、添字そえじ $$0$$0 から始はじまる配列はいれつに段階順だんかいじゅんで格納かくのうできる。添字そえじ $$i$$i の子この添字そえじは $$2i+1$$2i+1 と $$2i+2$$2i+2 である。

最小さいしょうヒープmin-heapは、完全二分木かんぜんにぶんぎの形状けいじょうをもち、各辺かくへんについて

が成立せいりつする。このヒープ不変条件ふへんじょうけんheap invariantにより、根ねは全要素ぜんようその最小鍵さいしょうかぎをもつ。実際じっさい、根ねから任意にんいの頂点ちょうてんへの道みちに沿そって不等式ふとうしきを推移的すいいてきに適用てきようすると、根ねの鍵かぎはその頂点ちょうてんの鍵かぎ以下いかである。ただし、兄弟間きょうだいかんや異ことなる部分木間ぶぶんぎかんの順序じゅんじょは規定きていされない。最大さいだいヒープは不等号ふとうごうを逆ぎゃくにした構造こうぞうである。

4基本操作きほんそうさと計算量けいさんりょう

• 最小値参照さいしょうちさんしょうは根ねを参照さんしょうするため $$\mathrm{\Theta }\left(1\right)$$\Theta(1) 時間じかんである。空からのヒープへの参照さんしょうは事前条件違反じぜんじょうけんいはんとする。
• 挿入そうにゅうでは配列末尾はいれつまつびに要素ようそを追加ついかし、親おやより鍵かぎが小ちいさい間あいだ、親おやと交換こうかんする。交換前こうかんまえに不変条件ふへんじょうけんを破やぶり得うる辺へんは追加要素ついかようそとその親おやの間あいだだけであり、この違反いはんを根方向ねほうこうへ移動いどうさせるため、停止時ていしじには不変条件ふへんじょうけんが回復かいふくする。一段いちだんの交換こうかんを $$O\left(1\right)$$O(1) とすれば、最悪時さいあくじは $$O\left(\log n\right)$$O(\log n) 時間じかんである。
• 最小値削除さいしょうちさくじょでは、空からでないことを事前条件じぜんじょうけんとする。$$n=1$$n=1 なら根ねを削除さくじょして空からのヒープとする。$$n>1$$n>1 なら根ねを削除さくじょし、末尾要素まつびようそを根ねへ移動いどうする。子こが存在そんざいし、かつ現在要素げんざいようそより小ちいさい鍵かぎの子こが存在そんざいする間あいだ、存在そんざいする子このうち最小鍵さいしょうかぎの子こと交換こうかんする。停止時ていしじには現在要素げんざいようそと子この間あいだにも不変条件ふへんじょうけんが成立せいりつし、交換こうかんしなかった部分ぶぶんの不変条件ふへんじょうけんは保存ほぞんされる。最悪時さいあくじは $$O\left(\log n\right)$$O(\log n) 時間じかんである。

最小さいしょうヒープは優先度付ゆうせんどつきキューpriority queueを実装じっそうできる。優先度付ゆうせんどつきキューは、要素ようその挿入そうにゅうと最小優先度要素さいしょうゆうせんどようその参照さんしょう・削除さくじょを提供ていきょうする抽象ちゅうしょうデータ型がたである。ヒープは全要素ぜんようそを整列順せいれつじゅんに保持ほじしないため、任意鍵にんいかぎの探索たんさくが高速こうそくになるとは限かぎらない。