1
アルゴリズムとデータ
構造
第6回演習解答
2015/11/18実施
アルゴリズムとデータ構造 2015
2
第６回演習解答(1/3)
[問題] 長さnの整数の配列A[0],A[1],...,A[n-1]において、要素の大きい方からm(<n)
個だけA[0],A[1],...,A[m-1]に大きい順に格納するアルゴリズムを作りたい。
void heapify(int i,int n,int A[])
void makeheap(int A[],int n)
/* A[2i+1]とA[2i+2]を根とするヒープ及びA[i]を、
/* A[0],...A[n-1]がヒープを
A[i]を根とするヒープに統合する */
構成するように並び換える */
{ int j;
{ int i;
j=2*i+1;
/* j:左の子 */
for(i=n/2-1;i>=0;i--) {
if(j>=n) return; /* 子がない場合は何もしない */
heapify(i,n,A);
if(j+1<n) {
/* 右の子もいる場合 */
}
if(A[j]>A[j+1]) { /* 右の子と左の子で要素の小さい方をjとする */
return;
j=j+1;
}
}
void swap(int i,int j,int A[]){
}
int temp;
temp=A[i]; A[i]=A[j]; A[j]=temp; if(A[j]<A[i]) { /* 子の方が小さい場合 */
swap(i,j,A);
/* 親子の入れ換え */
return;
heapify(j,n,A); /* A[j]から下がヒープの条件を満たすようにする */
}
}
return;
}
図１：ヒープを構成するアルゴリズム
2015/11/18実施
アルゴリズムとデータ構造 2015
第６回演習解答(2/3)
3
(a)図１のアルゴリズムを使って次の配列Aがヒープを構成するように並び換えよ。また、そ
のときのAの要素間の比較回数を求めよ。ただし、makeheap(A,10)を実行したものとする。
7 3 2 8 4 6 1 9 0 5
7 3 2 0 4 6 1 9 8 5
7
8
9
2
4
05
6
3
1
0
2
4
①
9
85
7 0 1 3 4 6 2 9 8 5
7
7
3
③
7 3 1 0 4 6 2 9 8 5
6
3
⑦
⑤
0
1
⑪
1
4
6
0
2
9
85
9
②
1
6
2
85
⑧
0 3 1 7 4 6 2 9 8 5
0 7 1 3 4 6 2 9 8 5
0
比較回数１５回
3
7
9
⑮4
85
⑭
2015/11/18実施
⑩
⑨4
3
⑥
④
7
0
1
7
⑬
6
2
3
9
1
4
6
2
⑫
85
アルゴリズムとデータ構造 2015
第６回演習解答(3/3)
4
(b)長さnの整数の配列A[0],A[1],...,A[n-1]において、要素の大きい方からm(<n)個だけ
A[0],A[1],...,A[m-1]に大きい順に格納するプログラムをmakeheapとheapifyの２つの手続
きを使ってC言語で書け。ただし、mサイズのヒープしか作らない効率のよいアルゴリズム
を考えよ。また、そのアルゴリズムの最悪時間計算量のオーダーを求めよ。
int i;
makeheap(A,m);
for(i=m;i<n;i++) {
if(A[i]>A[0]) {
A[0]=A[i];
heapify(0,m,A);
}
}
for(i=m-1;i>0;i--) {
swap(0,i,A);
heapify(0,i,A);
}
2015/11/18実施
O(m)
O((n-m)logm)
O(nlogm) (<O(nlogn))
O(mlogm)
アルゴリズムとデータ構造 2015
© Copyright 2024 ExpyDoc
