#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()
の機能・動作に付いて教えてください
(書き間違いがあるかもしれませんので容赦ください)
No.6ベストアンサー
- 回答日時:
> 0,2,4,6,8,10,12,14,16,18のヒープと
> 0,2,4,6,8,10,14,12,16,18のヒープは違うのですね?
> つまり初期条件によってヒープ結果は違ってくるのですね?
そういうことになりますかねぇ。
#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の意味がなんとなくわかってきました
ありがとうございました
No.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 …
No.4
- 回答日時:
あかん、思い切り突っ込まれてる (^^;
No.1 の回答は無視して。
どうしたらああいう説明になるんでしょうね。
No.1 にある SGI のドキュメントの Notes を読んでもらった方が良い。
英語が厳しいのなら、参考URL の microsoft のページの概説でも。
# いや、面目ない
参考URL:http://www.microsoft.com/japan/developer/library …
No.3
- 回答日時:
> SGI のドキュメントを見る限りでは、iterator が container が random access に適した
> ものかどうか分からない (iterator が抽象化している) ので、sort をやりやすくするように、
> randam access に適した形にする、という意味があります。
SGIのドキュメントからは、このような解釈は導き出せないのですが...
No.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 なので、質問にあるソースだと...
というわけで、この説明には疑問が残ります。
この回答への補足
0,2,4,6,8,10,12,14,16,18のヒープと
0,2,4,6,8,10,14,12,16,18のヒープは違うのですね?
つまり初期条件によってヒープ結果は違ってくるのですね?
よろしくお願いします
No.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
この回答への補足
やっぱり書き間違いがあったので訂正します
ついでに分かりやすく数字にしました
#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の機能とともに解説していただければ幸いです
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C++初心者です stirng 2 2022/09/20 20:43
- C言語・C++・C# C++プログラミングコードにポリモーフィズムを取り入れ方を教えてください。 2 2023/06/09 11:17
- C言語・C++・C# C++のcinの動作 5 2023/02/26 00:13
- C言語・C++・C# プログラミングの授業の課題です 1 2023/01/17 22:15
- C言語・C++・C# このプログラミング誰か教えてくれませんか 1 2022/06/02 15:27
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
- C言語・C++・C# 並列プログラミングのπ計算について 1 2022/07/16 22:30
- C言語・C++・C# 質問です 下記のコードを分かりやすく解説お願いします 初心者です #include ‹stdio.h 3 2022/05/26 22:03
- C言語・C++・C# c言語配列の結合についてです。 なぜうまくいかないのでしょうか。 #include <stdio.h 4 2022/05/30 22:42
- C言語・C++・C# c言語でユーザ関数を利用して入力された文字列を反転させるプログラムを作りたいです。 3 2023/01/29 19:47
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
【ヒトの神秘】美男美女から何...
-
input type="hidden"で取得した...
-
質問1.
-
2個のFormを横並びにしたい
-
Bootstrap レスポンシブ textarea
-
inputタグはformタグで必ず囲む...
-
【C++】Vector、listの要素比較...
-
<object>
-
角丸画像の背景色を透明にした...
-
テキストボックスの中にリンク...
-
HTMLでTextareaを横に2つ並べ...
-
HTMLページ上でiframeを最前面...
-
改行ほどは行かないけど、若干...
-
親要素・子要素
-
マージソートの計算量について-...
-
YouTubeでこのくらいの再生回数...
-
<div align="center">を使わず...
-
textareaの幅を画面と合わせたい
-
青空文庫のルビ
-
htmlの文字が縦書きになる
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
【ヒトの神秘】美男美女から何...
-
超音波で洗脳。
-
質問1.
-
smallにtext-allignが効かない
-
含む含まないという概念自体の...
-
NからZへの全単射を具体的に構...
-
角丸画像の背景色を透明にした...
-
タグは大文字と小文字どちらが...
-
改行ほどは行かないけど、若干...
-
「諸要素」とはどういう意味で...
-
2個のFormを横並びにしたい
-
input type="hidden"で取得した...
-
textareaの幅を画面と合わせたい
-
CSS:overflow要素の印刷について
-
親要素・子要素
-
テキストボックスの中にリンク...
-
emとstrongの反対
-
cssのdisplay:block
-
border: noneでボタンの境界線...
-
tdに対してmin-heightの定義、...
おすすめ情報