アルゴリズムとデータ構造 第6回演習解答 2015/11/18実施 アルゴリズムとデータ構造 2015
第６回演習解答(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[]) /* A[2i+1]とA[2i+2]を根とするヒープ及びA[i]を、 A[i]を根とするヒープに統合する */ { int j; j=2*i+1; /* j:左の子 */ if(j>=n) return; /* 子がない場合は何もしない */ if(j+1<n) { /* 右の子もいる場合 */ if(A[j]>A[j+1]) { /* 右の子と左の子で要素の小さい方をjとする */ j=j+1; } if(A[j]<A[i]) { /* 子の方が小さい場合 */ swap(i,j,A); /* 親子の入れ換え */ heapify(j,n,A); /* A[j]から下がヒープの条件を満たすようにする */ return; void makeheap(int A[],int n) /* A[0],...A[n-1]がヒープを 構成するように並び換える */ { int i; for(i=n/2-1;i>=0;i--) { heapify(i,n,A); } return; void swap(int i,int j,int A[]){ int temp; temp=A[i]; A[i]=A[j]; A[j]=temp; 図１：ヒープを構成するアルゴリズム 2015/11/18実施 アルゴリズムとデータ構造 2015
第６回演習解答(2/3) (a)図１のアルゴリズムを使って次の配列Aがヒープを構成するように並び換えよ。また、そのときのAの要素間の比較回数を求めよ。ただし、makeheap(A,10)を実行したものとする。 7 3 2 8 4 6 1 9 5 7 3 2 4 6 1 9 8 5 7 3 1 4 6 2 9 8 5 7 1 3 4 6 2 9 8 5 7 7 7 ⑪ 7 3 2 3 1 3 2 ⑦ ⑤ 1 ③ ⑩ 8 4 6 1 4 6 2 4 6 1 3 ⑨ 4 6 2 ⑥ ① 9 5 9 8 5 9 8 5 ④ 9 8 5 ② ⑧ 3 1 7 4 6 2 9 8 5 7 1 3 4 6 2 9 8 5 比較回数１５回 3 1 7 1 ⑬ 7 ⑮ 4 6 2 3 4 6 2 9 8 5 ⑫ 9 8 5 ⑭ 2015/11/18実施 アルゴリズムとデータ構造 2015
第６回演習解答(3/3) (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); O(m) O((n-m)logm) O(nlogm) (<O(nlogn)) O(mlogm) 2015/11/18実施 アルゴリズムとデータ構造 2015