2.5 ヒープ
ヒープとは
この部分木で一番
大きい値は根の14
１６
この部分木で一番
大きい値は根の10
１４
１０
１１
４
９
２
６
３
８
どの部分木でもその中で
一番大きい値は根にある
ヒープとは
１
h[i]⇔v
２
３ １６
h[2i]⇔vの左の子
４
５
６
７ h[2i+1]⇔vの右の子
１４
１０
８
９ １０
1 １１2 3 4 ９5
16 14 10 11 9
４
２
６
6
3
7３
8
8
4
9８ 10
2 6
ヒープの再構成
１６
１４
１０
１１
４
９
２
６
３
８
ヒープの再構成
ヒープが壊れる
１６ 最大要素を取り出す
１４
１０
１１
４
９
２
６
３
８
ヒープの再構成
６
１４
１０
１１
４
９
２
６
３
８
一番端のデータを
トップに移動
ヒープの再構成
部下の強い方と
ポジションを争う
６
１４
１１
４
１０
９
２
３
８
ヒープの再構成
負けたので降格
６
１４
１１
４
１０
９
２
３
８
ヒープの再構成
部下の強い方と
ポジションを争う
１４
６
１１
４
１０
９
２
３
８
ヒープの再構成
負けたので降格
１４
６
１１
４
１０
９
２
３
８
ヒープの再構成
部下の強い方と
ポジションを争う
１４
１１
６
４
１０
９
２
３
８
ヒープの再構成
勝ったので、そこが
実力通りのポジション
１４
１１
６
４
１０
９
２
３
８
ヒープが完成したので
再構成終了
P32のdownheapの動き
１６
６
getheap h[1]:=h[n]
１４
１０
１１
４
９
２
６
３
８
一番端のデータを
トップに移動
P32のdownheapの動き
v
６
６
h[k]
１４
１１
４
１０
９
２
３
８
根にあるデータを
変数vに保存
P32のdownheapの動き
v
６
h[k]
１４ h[i]
１１
４
９
２
１０ h[i+1]
３
８
強い方と比較
P32のdownheapの動き
v
６
h[k]
１４ h[i]
１１
４
９
２
１０ h[i+1]
３
８
部下が勝ったので
部下を上に上げる
P32のdownheapの動き
v
６
１４
１０
h[k]
１１
４
h[i]
２
９
３
８
h[i+1]
強い方と比較
P32のdownheapの動き
v
６
１４
１０
h[k]
１１
４
h[i]
２
９
３
８
h[i+1]
部下が勝ったので
部下を上に上げる
P32のdownheapの動き
v
６
１４
１１
h[k]
４
h[i]
２
h[i+1]
１０
９
３
８
強い方と比較
P32のdownheapの動き
v
６
finish
１４
１１
h[k]
４
h[i]
２
h[i+1]
１０
９
３
８
勝ったので
ポジションに入る
P33のupheapの動き
１６
upheap h[n]:=13
１０
１1
９
6
４
２
１３
３
８
一番最後に１3を追加
P33のupheapの動き
v
１３
１６
１０
１1
９
6
４
２
１３
３
８
一番最後のデータを
変数vに保存
P33のupheapの動き
v
１３
１６
１０
１1
９ h[i] ３
6
４
２
上司と比較
８
P33のupheapの動き
v
１３
１６
１０
１1
９
6
４
２
３
８
上司が負けたので
上司を下げる
P33のupheapの動き
v
１３
１６
１０
１1 h[i]
３
6
４
２
９
上司と比較
８
P33のupheapの動き
v
１３
１６
１０
１1
３
6
４
２
９
８
上司が負けたので
上司を下げる
P33のupheapの動き
v
１３
１６ h[i]
１０
１1
6
４
２
９
３
上司と比較
８
P33のupheapの動き
v
１３
１６
１０
finish
１1
6
４
２
９
３
８
負けたので
ポジションに入る
downheapとupheapの時間計算量
• それぞれの計算量は何に依存するか？
• 教科書のP33を参考にせよ
2.6 集合の表現と演算
集合の基本演算
• データを集合とみなす
⇒ データの操作 ⇔ 集合の演算
• 基本演算
リスト
–
–
–
–
–
menber(x,S)
search
O(|S|)
adjoin(x,S)
search + insert
O(|S|)
remove(x,S)
search + delete
O(|S|)
union(S1,S2)
O(|S1|・ |S2|)
intersection(S1,S2)
O(|S1|・ |S2|)
ビットベクトル
• 第i要素の有無で、i番目のビットが１,０
第１要素
第３要素
第５要素
第７要素
第２要素
第４要素
第６要素
第８要素
集合A
1
1
0
1
∩ /∪
集合B
0
1
1
1
2
4
6
8
集合A
0
1
0
1
0
1
and /or
0
1
1
2
3
6
5
8
集合B