2014-8 - Researchmap

THE UNIVERSITY OF TOKYO
数理情報工学演習第一Ｃ
プログラミング演習 (第8回 )
2014/06/02
DEPARTMENT OF MATHEMATICAL INFORMATICS
1
THE UNIVERSITY OF TOKYO
今日の内容:
 プライオリティキュー
 ヒープ
 課題：ヒープソート
2
THE UNIVERSITY OF TOKYO
プライオリティキュー
要素の集合 S を保持するためのデータ構造
各要素はキーと呼ばれる値を持つ
次の操作をサポートする
INSERT(S,x): S に要素 x を追加する
MAXIMUM(S): 最大のキーを持つ S の要素を返す
EXTRACT_MAX(S): 最大のキーを持つ S の要素を削除し，その値を返す
単純なキューは，要素を入れた順番に出力するが，
プライオリティキューでは優先度の高い順に出力する
3
THE UNIVERSITY OF TOKYO
ヒープ
プライオリティキューはヒープで実現できる
ヒープ：完全2分木とみなせる配列
木の各節点は配列の要素に対応
木は最下位レベル以外の全てのレベルの点が完全に詰まっている
最下位のレベルは左から順に詰まっている
1
16
2
3
1 2 3 4 5 6 7 8 9 10
14
10
4
5
6
7
16 14 10 8 7 9 3 2 4 1
8
7
9
3
8
9 10
1
4
4 2
THE UNIVERSITY OF TOKYO
ヒープを表す構造体
typedef struct {
int max_size;
int size;
data *A;
} HEAP;
// 配列 A に格納できる最大要素数
// ヒープに格納されている要素の数
// 要素を格納する配列
ヒープに後から要素を追加する場合があるとき，配列 A は大きいものを
確保しておく
5
THE UNIVERSITY OF TOKYO
max_size: 配列 A に格納できる最大要素数
size: H に格納されているヒープの要素数
size  max_size
1
16
木の根： A[1]
節点の添え字が i のとき
4
親 PARENT(i) = i / 2
左の子 LEFT(i) = 2 i
右の子 RIGHT(i) = 2 i + 1
2
14
8
8
2
9 10
1
4
3
10
5
7
6
9
7
3
木の高さは (lg n)
6
THE UNIVERSITY OF TOKYO
ヒープ条件 (Heap Property)
根以外の任意の節点 i に対して
A[PARENT(i)]  A[i]
つまり，節点の値はその親の値以下
1
16
ヒープの最大要素は根に格納される
4
2
14
8
8
2
7
9 10
1
4
3
10
5
7
6
9
7
3
THE UNIVERSITY OF TOKYO
ヒープの操作
heapify: ヒープ条件を維持する.
build: 入力の配列からヒープを構成する. O(n)時間.
heapsort: 配列をソートする. O(n lg n) 時間.
extract_max: ヒープの最大値を取り出す. O(lg n) 時間.
insert: ヒープに値を追加する. O(lg n) 時間.
8
THE UNIVERSITY OF TOKYO
ヒープ条件の維持
heapify(H,i): A[i] を根とする部分木がヒープになるようにする.
ただし LEFT(i) とRIGHT(i) を根とする2分木はヒープと仮定.
void heapify(HEAP *H, int i)
{
int l, r, largest, heap_size;
data tmp, *A;
A = H->A; heap_size = H->heap_size;
l = LEFT(i); r = RIGHT(i);
if (l <= heap_size && A[l] > A[i]) largest = l; // A[i] と左の子で大きい
else largest = i;
// 方をlargestに
if (r <= heap_size && A[r] > A[largest])
// 右の子の方が大きい
largest = r;
if (largest != i) {
tmp = A[i]; A[i] = A[largest]; A[largest] = tmp; // A[i]を子供と入れ替える
heapify(H, largest);
}
}
9
THE UNIVERSITY OF TOKYO
heapify(A,2)
4
9 10
1
8
heapify(A,9)
4
3
10
5
7
6
9
9 10
1
4
7
3
4
2
14
4
8
2
1
16
9 10
1
8
3
10
5
7
6
9
7
3
1
16
2
14
8
8
10 2
heapify(A,4)
2
4
14
8
2
1
16
3
10
5
7
6
9
7
3
THE UNIVERSITY OF TOKYO
ヒープの構築
heapifyでは左右の部分木がヒープである必要がある
全体をヒープにするには，2分木の葉の方からヒープにしていけばいい
HEAP *heap_build(int n, data *A, int max_size)
{
int i;
HEAP *H;
mymalloc(H, 1);
H->max_size = max_size;
H->size = n;
H->A = A;
for (i = n/2; i >= 1; i--) {
heapify(H,i);
}
}
11
THE UNIVERSITY OF TOKYO
A 4 1 3 2 16 9 10 14 8 7
1
4
2
3
1
3
4
5
6
7
2
16
9
10
8
9 10
14
7
8
heapify(A,5)
1
4
2
3
1
3
4
5
6
7
14
16
9
10
8
9 10
2
7
8
heapify(A,3)
12
1
4
4
2
1
3
3
2
8
14
9 10
7
8
5
16
6
9
7
10
heapify(A,4)
1
4
4
2
1
3
10
14
8
2
9 10
7
8
5
16
6
9
7
3
heapify(A,2)
THE UNIVERSITY OF TOKYO
1
4
4
2
16
14
8
2
13
1
16
9 10
1
8
3
10
5
7
6
9
7
3
heapify(A,1)
4
2
14
8
8
2
9 10
1
4
3
10
5
7
6
9
7
3
THE UNIVERSITY OF TOKYO
ヒープへの挿入
sizeを1つ増やし，新しい要素を配列の末尾に追加する
末尾の要素とその親節点の間でヒープ条件が満たされていない可能性がある
満たされていなければ両者を入れ替える
親節点の値が大きくなったので，その親でヒープ条件を調べる
最悪時は根まで入れ替える必要あり
O(log n) 時間
4
2
14
8
8
2
1
16
9 10
1
4
3
10
5
7
6
9
7
3
11
12
14
THE UNIVERSITY OF TOKYO
ヒープソート
まずヒープを作る
すると最大要素が A[1] に入る
A[1]とA[n]を交換すると，最大要素がA[n]に入る
ヒープのサイズを1つ減らしてヒープを維持する
15
void heapsort(int n, data *A)
{
int i;
data tmp;
HEAP *H;
H = heap_build(n,A,n);
for (i = n; i >= 2; i--) {
tmp = A[1]; A[1] = A[i]; A[i] = tmp; // 根と最後の要素を交換
H->size = H->size - 1;
heapify(H,1);
}
}
THE UNIVERSITY OF TOKYO
1
16
2
14
4
8
8
2
1
14
9 10
1
4
3
10
5
7
6
9
7
3
2
8
4
3
10
5
7
4
8
2
9
1
3
9
4
8
2
16
1
9
2
8
5
7
14
16
7
3
16
1
10
4
6
9
6
1
2
8
4
7
3
3
3
5
7
4
10
14
6
1
7
2
16
THE UNIVERSITY OF TOKYO
1
8
2
7
4
3
3
5
2
4
10
1
7
6
1
4
3
3
5
2
1
9
16
14
2
4
10
14
10
17
1
3
2
2
7
14
2
2
3
3
1
16
9
16
1
4
4
8
8
3
1
4
9
10
7
14
8
9
16
THE UNIVERSITY OF TOKYO
1
2
1
1
2
1
4
10
7
14
2
3
16
8
3
4
9
10
7
14
8
9
16
A 1 2 3 4 7 8 9 10 14 16
18
THE UNIVERSITY OF TOKYO
計算量
heap_build: O(n) 時間
heapify: O(n lg n) 時間
全体で O(n lg n) 時間
19
THE UNIVERSITY OF TOKYO
課題1: ヒープソート
• ヒープを用いて整数のソートを行うプログラムを作成する
20
THE UNIVERSITY OF TOKYO
課題2
• ヒープを用いて (key, value) のペアを key でソートするプログラム
• ヒープの構造体の中に，(key, value) の構造体の配列を格納する
• 要素の大小関係の比較のところを書き換える必要あり
if (l <= heap_size && A[l] > A[i]) largest = l;
ここを key の比較にする (他の場所も同様)
• 可能ならソースコードを課題1と共通化する．分からなければ別で良い
• 課題1,2共に 6/6(金) の正午までに提出
• 宛先：[email protected]
21
THE UNIVERSITY OF TOKYO
ヒント
• 大小の比較部分を汎用的にするには2つ方法がある
• 方法1: ハッシュ関数のときと同じように，外部の比較関数を使う
– if (l <= heap_size && greater(&A[l], &A[i])) largest = l;
int greater(int *x, int *y) {
これは整数比較用の関数
return *x - *y;
構造体の場合は変更する
}
– 利点: heap.c を再コンパイルしなくて良い
– 欠点: 関数呼び出しによる速度低下
• 方法2: マクロを使う
#define GREATER(x, y) ((*(x))>(*(y)))
– if (l <= heap_size && GREATER(&A[l], &A[i])) largest = l;
22
– 利点と欠点: 方法1と反対
THE UNIVERSITY OF TOKYO

Download Report