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

ということですが
ｍａｋｅ＿ｈｅａｐ（）
の機能がわかりません
ｍａｋｅ＿ｈｅａｐ（）
の機能・動作に付いて教えてください
（書き間違いがあるかもしれませんので容赦ください）

回答No.6

επιστημη（@episteme） · ベストアンサー

> ０，２，４，６，８，１０，１２，１４，１６，１８のヒープと
> ０，２，４，６，８，１０，１４，１２，１６，１８のヒープは違うのですね？
> つまり初期条件によってヒープ結果は違ってくるのですね？

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

お礼

#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]<<" ";
}

をＢｏｒｌａｎｄ無償コンパイラでコンパイル実行すると

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

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

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

回答No.5

επιστημη（@episteme）

> 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

回答No.4

a-kuma

あかん、思い切り突っ込まれてる　(^^;
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

回答No.3

επιστημη（@episteme）

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

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

回答No.2

επιστημη（@episteme）

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

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

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

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

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

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

補足

０，２，４，６，８，１０，１２，１４，１６，１８のヒープと
０，２，４，６，８，１０，１４，１２，１６，１８のヒープは違うのですね？
つまり初期条件によってヒープ結果は違ってくるのですね？

よろしくお願いします

回答No.1

a-kuma

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

補足

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

#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
です

どうしてこのような並びになるかｍａｋｅ＿ｈｅａｐの機能とともに解説していただければ幸いです