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

date2026-07-14document_iddoc_6d4933a65f37e16b776fa98af494e734description根付き木の親子関係と深さを定義し、二分ヒープの不変条件、基本操作、計算量を説明する。prerequisitesグラフの基本 / スタックとキューの基本 / 計算量の基本 / 再帰の基本type講義statusactive

algorithmdata-structuresundergraduatelecture

data/lecture/information/graph/graph-basics.lecture.n.md data/lecture/information/algorithm/data-structures/data-structures-portal.lecture.n.md

1導入どうにゅう

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

2根付ねつき木ぎ

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

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

3二分にぶんヒープ

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

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

key (parent (v)) \leq key (v)

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

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

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

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

Tree and Heap Basics

data/lecture/information/graph/graph-basics.lecture.n.md data/lecture/information/algorithm/data-structures/data-structures-portal.lecture.n.md

1Introduction

This lecture defines parent-child relationships and depth in rooted trees and explains the invariant, basic operations, and complexity of binary heaps.

2Rooted trees

A tree is an undirected graph in which there is exactly one path between every pair of vertices. A rooted tree designates one vertex of a tree as its root. For each non-root vertex $v$ , the parent of $v$ is the vertex immediately after $v$ on the path from $v$ to the root. A vertex whose parent is $v$ is a child of $v$ . The root has no parent.

The depth of a vertex $v$ is the number of edges on the path from the root to $v$ . The root has depth $0$ , and a child has depth one greater than its parent. The height of a tree is the maximum depth of its vertices. A rooted tree in which every vertex has at most two children is a binary tree.

3Binary heaps

A complete binary tree with $n$ elements has every level except possibly the last filled, and its last-level vertices occupy consecutive positions from the left. Its height is $⌊ \log_{2} n ⌋$ for $n > 0$ . It can be stored in level order in an array indexed from $0$ , where the children of index $i$ have indices $2 i + 1$ and $2 i + 2$ .

A min-heap has the shape of a complete binary tree and satisfies

key (parent (v)) \leq key (v)

for every edge. This heap invariant places an element with a minimum key at the root: applying the inequalities transitively along the path from the root to any vertex shows that the root key is no greater than that vertex's key. The invariant does not order siblings or vertices in different subtrees. A max-heap reverses the inequality.

4Basic operations and complexity

Finding the minimum examines the root and therefore takes $Θ (1)$ time. Accessing an empty heap violates a precondition.
Insertion appends an element and swaps it with its parent while its key is smaller. Before a swap, only the edge from the inserted element to its parent can violate the invariant. Each swap moves this possible violation toward the root, so the invariant is restored when the process stops. If one level of swapping takes $O (1)$ time, the worst-case time is $O (\log n)$ .
Deleting the minimum requires a nonempty heap. If $n = 1$ , remove the root and leave an empty heap. If $n > 1$ , remove the root and move the last element to the root. While a child exists with a key smaller than the current element, swap the current element with the minimum-key child among the children that exist. On termination the invariant also holds between the current element and its children, while all untouched edges have preserved it. The worst-case time is $O (\log n)$ .

A min-heap can implement a priority queue, an abstract data type that supports insertion and access to or deletion of an element with minimum priority. A heap does not maintain all elements in sorted order, so it does not necessarily provide fast search for an arbitrary key.