こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

make_heap()が分かりません

#include <iostream>
#include <vector>
#include <algotithm>
using namespace std;
int main()
{
vector<char> v;
int i;
for(i=0;i<20;i+=2)v.push_back('A'+i);
couti<<"sequence before building heap:\n";
for(i=0;i<v.size();i++)cout<<v[i]<<" ";
cout<<"\n\n";
make_heap(v.begin(),v.end()); //?
couti<<"sequence after building heap:\n";
for(i=0;i<v.size();i++)cout<<v[i]<<" ";
cout<<"\n\n";
}

の結果が

sequence before building heap:
A C E G I K M O Q S

sequence after building heap:
S Q M O I K E A G C

ということですが
make_heap()
の機能がわかりません
make_heap()
の機能・動作に付いて教えてください
(書き間違いがあるかもしれませんので容赦ください)

投稿日時 - 2002-12-12 02:41:29

QNo.425935

困ってます

質問者が選んだベストアンサー

> 0,2,4,6,8,10,12,14,16,18のヒープと
> 0,2,4,6,8,10,14,12,16,18のヒープは違うのですね?
> つまり初期条件によってヒープ結果は違ってくるのですね?

そういうことになりますかねぇ。

投稿日時 - 2002-12-12 16:20:00

お礼

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void main()
{
 vector<int> v;
 int i;
 for(i=0;i<10;i++)v.push_back(i);
 cout<<"heap(";for(i=0;i<(int)v.size();i++)cout<<v[i]<<" "; cout<<")=";

 make_heap(v.begin(),v.end()); //?
 for(i=0;i<(int)v.size();i++)cout<<v[i]<<" ";

 v[0]=0;v[1]=1;v[2]=2;v[3]=3;v[4]=4;v[5]=5;v[6]=7;v[7]=6;v[8]=8;v[9]=9;
 cout<<"heap(";for(i=0;i<(int)v.size();i++)cout<<v[i]<<" ";cout<<")=";

 make_heap(v.begin(),v.end()); //?
 for(i=0;i<(int)v.size();i++)cout<<v[i]<<" ";
}

をBorland無償コンパイラでコンパイル実行すると

heap(0 1 2 3 4 5 6 7 8 9 )=9 8 6 7 4 5 2 0 3 1
heap(0 1 2 3 4 5 7 6 8 9 )=9 8 7 6 4 5 2 0 3 1

となりますから多分そうでしょう

heapの意味がなんとなくわかってきました
ありがとうございました

投稿日時 - 2002-12-13 04:21:28

このQ&Aは役に立ちましたか?

2人が「このQ&Aが役に立った」と投票しています

回答(6)

ANo.5

> No.1 にある SGI のドキュメントの Notes を読んでもらった方が良い。
> 英語が厳しいのなら、参考URL の microsoft のページの概説でも。

正しい説明は IS(International Standard:国際規格書) を読むのが一番でしょう。なんせ神様ですから。それによると、

- 先頭要素が一番でかい
- 先頭要素の削除および要素の追加にはO(logN)の時間計算量を要する

と'だけ'定義されており、その要件さえ満たせばシーケンス内での並びは実装依存ということになります。が、上記用件を満たすとなると必然的にNo.2のような構造にならざるを得ないはずです。

# 宣伝御免
# C++のディープな話題はcppll-ML(下記URL)へ。

参考URL:http://www.freeml.com/ctrl/html/MLInfoForm/cppll@freeml.com

投稿日時 - 2002-12-12 10:57:18

ANo.4

あかん、思い切り突っ込まれてる (^^;
No.1 の回答は無視して。

どうしたらああいう説明になるんでしょうね。
No.1 にある SGI のドキュメントの Notes を読んでもらった方が良い。

英語が厳しいのなら、参考URL の microsoft のページの概説でも。

# いや、面目ない

参考URL:http://www.microsoft.com/japan/developer/library/vclang/sample_heap_(STL_Sample).htm#_sample_stl_heap

投稿日時 - 2002-12-12 10:23:42

ANo.3

> SGI のドキュメントを見る限りでは、iterator が container が random access に適した
> ものかどうか分からない (iterator が抽象化している) ので、sort をやりやすくするように、
> randam access に適した形にする、という意味があります。

SGIのドキュメントからは、このような解釈は導き出せないのですが...

投稿日時 - 2002-12-12 09:39:11

ANo.2

v[1], v[2], ..... v[N] において、

v[i] >= v[2*i] かつ
v[i] >= v[2*i+1]

を満足するよう並べ替えられます。
したがって先頭要素が最大となります。

上記の条件を満たすシーケンス(要素の並び)を
heapといいます。先頭要素を取り除き、
末尾要素を先頭に置き、また上の条件を満たす
ように並び替える...を繰り返すことによって、
シーケンスをソートすることができます。
それがheap_sortです。


> vector は、もともと randam access しやすい
> container なので、質問にあるソースだと...

というわけで、この説明には疑問が残ります。

投稿日時 - 2002-12-12 07:06:47

補足

0,2,4,6,8,10,12,14,16,18のヒープと
0,2,4,6,8,10,14,12,16,18のヒープは違うのですね?
つまり初期条件によってヒープ結果は違ってくるのですね?

よろしくお願いします

投稿日時 - 2002-12-12 13:33:37

ANo.1

SGI のドキュメントを見る限りでは、iterator が container が random access に適した
ものかどうか分からない (iterator が抽象化している) ので、sort をやりやすくするように、
randam access に適した形にする、という意味があります。

vector は、もともと randam access しやすい container なので、質問にあるソースだと、
その効果は認められませんが、list や tree のような container を make_heap する
前と後で sort してみると、その効果が出ます。

# と、思います (^^;

参考URL:http://www.sgi.com/tech/stl/make_heap.html

投稿日時 - 2002-12-12 03:09:08

補足

やっぱり書き間違いがあったので訂正します
ついでに分かりやすく数字にしました

#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v;
int i;
for(i=0;i<10;i++)v.push_back(i);
cout<<"sequence before building heap:\n";
for(i=0;i<(int)v.size();i++)cout<<v[i]<<" ";
cout<<"\n\n";
make_heap(v.begin(),v.end()); //?
cout<<"sequence after building heap:\n";
for(i=0;i<(int)v.size();i++)cout<<v[i]<<" ";
cout<<"\n\n";
return 0;
}

結果は
sequence before building heap:
0 1 2 3 4 5 6 7 8 9

sequence after building heap:
9 8 6 7 4 5 2 0 3 1
です

どうしてこのような並びになるかmake_heapの機能とともに解説していただければ幸いです

投稿日時 - 2002-12-12 05:01:54