忙しい現代人の腰&肩のお悩み対策!

データ構造やアルゴリズムについての質問です。
「ヒープ」を用いてソートができたりすること、
ヒープへ挿入や、ヒープからの削除は分かるのですが、
そもそもヒープの作り方が分かりません。

≪作り方≫
ある要素の集合が与えられたとき、
1つ目の値をルートにもってくる
2つ目の値をルートと比較し、子≦ルートとなるように追加
3つ目の値をルートと比較し、子≦ルートとなるように追加
4つ目の値をルートの左の子と比較し、子≦ルートの左の子、かつルートとも比較
.....
という風に要素の集合から要素がなくなるまで続けるので正しいでしょうか?

それとも初めに与えられた要素の集合を
ひとまず要素数分の2分木構造に割り当て、
ヒープが成り立つように、あとから値の交換を
行うのでしょうか?

いま、要素の集団は配列のように順番が決まっているとして
考えています。

≪取り出しと削除≫
値の「取り出し」と「削除」は別物。という認識は正しいでしょうか?
(1)取り出し...末端の最も右の葉をルートにコピーし、ヒープを再構成。
⇒ルートの値を取り出す。
(2)削除...削除したい値を削除し、その子孫を繰り上げる。

詳しい方がおられましたら、ご指摘、アドバイス等
どうぞよろしくお願い致します。

このQ&Aに関連する最新のQ&A

A 回答 (3件)

配列として与えられたデータからヒープを作るだけなら


1. 空のヒープを作って 1つずつデータを追加する
2. 配列に対していろいろ処理して最終的にヒープにする
のどちらも可能です. やってることがわかりやすいのは 1 だけど 2 の方が速く, n個のデータがあるとき 1 が O(n log n) 時間に対して 2 は O(n) 時間.

でいちおう「取り出し」はそれでいいといえばいいです. ただし, 「末端の最も右の値をルートにコピーし、ヒープを再構成する」とはいってもその「末端の最も右」のノードは使わなくなってしまうので, 実務的には「末端の最も右の値とルートの値を交換してからヒープを再構成する」のが普通です. あと, そもそも「取り出す」といったときに「ルートの値をとってくる」だけで「ルートの値を取り除く」までは想定しない可能性があるので, もうちょっと正確な表現をすべきだとは思います.

「削除」ですが, 「削除したい値を削除し、削除した頂点以下のノードを再構成する」は (少なくとも素朴に読む限り) ダメです. TECHSCORE の絵でいうと, 2番の 21 という値を削除するときにその下の 5番と 6番だけをヒープとして作り直してもダメだよね. これも上の「取り出し」と同じように, 当該ノードを「末端の最も右の値」と交換してからヒープを作り直すのが自然かな.
    • good
    • 0
この回答へのお礼

回答頂きありがとうございます!
とても分かりやすい説明でした。

>TECHSCORE の絵でいうと, 2番の 21 という値を削除するときにその下の 5番と 6番だけをヒープとして作り直してもダメだよね.

確かにそうでした、ヒープは葉まですべて詰まっていなければ
いけませんもんね!

>「取り出し」と同じように, 当該ノードを「末端の最も右の値」と交換してからヒープを作り直すのが自然かな.

了解致しました!

お助けいただき、本当にありがとうございました。

お礼日時:2014/08/01 11:17

作り方自体はどっちでもいいです. 後者の方が速いけど.



「≪取り出しと削除≫」のところは.... 何を言っているのかわからない. 「取り出し」は「⇒」が意味不明だし (ヒープを再構成してからルートの値を取り出すということ?), 「削除」にしてもそれだけではヒープにならない.

この回答への補足

回答頂きありがとうございます!

>作り方自体はどっちでもいいです.
そうなんですか!?いろいろ調べたのですが
情報が錯そうしてこんがらがっていました。驚きです。
私の1つ目の方法は、「挿入の繰り返し」といった感じです。

>≪取り出しと削除≫~何を言っているのかわからない
言葉足らずで、すみません。
「取り出し」は、
ソートの際にヒープ完成後、ルートの値を取り出すことを言っています。
ルートの値を取り出し、末端の最も右の値をルートにコピーし、ヒープを再構成する。その繰り返しでヒープソートができるのだろうと思っています。が正しいでしょうか?
「削除」は、削除したい値を削除し、削除した頂点以下のノードを再構成するだけではだめでしょうか?

お手数をお掛けしてしまい、大変恐縮ですが
よろしくお願い致します。

補足日時:2014/07/31 15:21
    • good
    • 0

枝分かれが2分岐でしかないツリー構造のうちでも「2分木」というもので、



その根っこ(といいながら良く図の上側にある)のほうが枝の先(下側)よりも小さい、逆に言えば、枝の先(下側)のほうが大きいような並びでツリーができている

というのがヒープです。あとは、ヒープソートの図解を見たほうが、イメージしやすいかと思います。

9.ソーティング(ヒープソート) | TECHSCORE(テックスコア)
http://www.techscore.com/tech/C/9.html/

ヒープソート
http://www.ics.kagoshima-u.ac.jp/~fuchida/edu/al …

ヒープソート - Google 検索
http://www.google.co.jp/search?q=%E3%83%92%E3%83 …

この回答への補足

回答頂きありがとうございます!

「挿入」と「ヒープの作成」が区別できずにいます。

9.ソーティング(ヒープソート) | TECHSCORE(テックスコア)より
「最初はどの部分木もヒープではありませんが、」一番末端の右端にある部分木(9.1の図の場合は「4」を根とする部分木)から順に上記の処理を実行していけば、木全体がヒープになります。
ということは、
私の上記の方法(=挿入の繰り返し)は間違っているという認識でよろしいでしょうか?

お手数をお掛けしますが、
よろしくお願い致します。

補足日時:2014/07/31 15:09
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qオペアンプ/反転増幅器/頭打ち

オペアンプの反転増幅器における特性について質問します。

ある値で入力電圧をかけ、出力電圧をテスターやオシロスコープで波形を見ると、ある値で頭打ちになってしまいます。オペアンプには、規定の電源電圧において正常に動作する限界値(出力が飽和する電圧)があると耳にしましたが、どういうことでしょうか?

オペアンプについて熟知しておらず、曖昧な質問で申し訳ありません。
よろしくお願い致します。

Aベストアンサー

>オペアンプには、規定の電源電圧において正常に動作する限界値(出力が飽和する電圧)があると耳にしましたが、どういうことでしょうか?

まさに言われる通り、ある電圧で出力が飽和してしまうってことです。
まず、当然のことながら、オペアンプはかけられた電源電圧以上の電圧を出力することはできませんから、どんなに頑張っても、電源電圧でオペアンプの出力は飽和してしまいます。

実際には、一般的なオペアンプは、電源電圧まで出すことができず、それより低い電圧で出力が飽和してしまいます。
オペアンプを(特に増幅目的で)使うときには、出力が飽和してしまわないように、入力の大きさを考えて増幅率を設計する必要があります。

Q閉ループゲイン 開ループゲイン

オペアンプの閉ループゲイン、開ループゲインとはそもそも何なのでしょうか?
根本的なとこがわかりません。
どなたかよろしくお願いします。

Aベストアンサー

[図6.1-41]を見てください。
これが開(オープン)ループゲインです。(青色)
(フィードバックをかけていないときの利得ー周波数特性)
http://my1.interlink.or.jp/~md0858/series4/densi0613.html

70Hzくらいまでは100dBの利得がありますが、より高い周波数では-6dB/oct(=-20dB/decade)でどんどん下がっていき、7MHzくらいで0dBとなります。
(最大利得と周波数特性はオペアンプの種類によって異なるが、この”傾向”はすべてのオペアンプについて言える)

[図6.1-43]を見てください。
例えば80dB(60dB)のフィドバックをかけたとすると、利得は20dB(40dB)になりますが、利得一定の周波数幅がうんと広くなることにお気づきでしょうか?
これが閉ループゲインです。

一般に、オペアンプの開ループゲインは100dB以上ありますが、これを開ループで使うことは滅多にありません。
周波数特性が問題にならないコンパレータのときくらいのものです。

参考URL:http://my1.interlink.or.jp/~md0858/series4/densi0613.html

[図6.1-41]を見てください。
これが開(オープン)ループゲインです。(青色)
(フィードバックをかけていないときの利得ー周波数特性)
http://my1.interlink.or.jp/~md0858/series4/densi0613.html

70Hzくらいまでは100dBの利得がありますが、より高い周波数では-6dB/oct(=-20dB/decade)でどんどん下がっていき、7MHzくらいで0dBとなります。
(最大利得と周波数特性はオペアンプの種類によって異なるが、この”傾向”はすべてのオペアンプについて言える)

[図6.1-43]を見てください。
例えば80dB(60...続きを読む

Qオペアンプの開ループ利得

オペアンプの開ループ利得が小さいとどのような不都合が起こるのでしょうか?
どなたか教えてください

Aベストアンサー

例えば、非反転増幅器のゲインが 1+(R2/R1) と表わされるのはよくご存知と思います(記号の意味省略)。しかし、これは近似であって、OPアンプの開ループ利得Aをちゃんと計算に入れれば、(R1+R2)/((R1+(R1+R2)/A) が正しいゲインになります(ただし入力抵抗十分大は仮定)。Aが十分大きくない場合、始めの近似式と、実際のゲインの違いが顕著になります。

-このようなことは、OPアンプを扱った大抵の本に出ていると思います。

Q反転増幅器の周波数特性

入力電圧V1=300mV、R1=10kΩ、Rf=100kΩの反転増幅回路で周波数を100Hzから200kHzまで徐々に変化させていくと、10kHz以降から位相差が生じて、出力電圧、利得が減少しはじめました。どうしてこんなことが起きるのでしょうか?その根拠がわかりません・・・
そしてなぜ10kHzから生じたのかという根拠もわかりません。
どなたかご回答の程よろしくお願いします。

Aベストアンサー

関連する質問を紹介しますので、この回答を参考にレポートを書いてください。

μPC741というオペアンプを使って反転増幅の周波数特性をG=0,10,20dBと3種類測定しました。
(1)3種類とも利得が-3dBになる高域遮断周波数が約40kHzになりました。理論値と比較したいのですが理論式の導出がわからない
(2)周波数をあげると生じる入出力の位相差の原因とその理論式(たぶんスルーレートが関係すると思うのですが)
(3)位相差と利得の低下にはどんな関係があるのか http://okwave.jp/qa3510524.html

基本的な反転増幅回路における周波数特性が右下がりになる理由を理論的に説明したいのですが、回路にコンデンサが使われていないので、カットオフ周波数が求められなくて困っています。オペアンプは751です。右下がりになる理由はカットオフとオペアンプの周波数特性によるものですよね? http://okwave.jp/qa3048059.html

非反転増幅、反転増幅の回路実験を行ったのですが、1kHzや100kHz を入力すると、約10倍の増幅が確認できたのに対し、1MHzを入力した場合、約1.2倍となりほとんど増幅が確認できませんでした。 これはなぜでしょうか http://okwave.jp/qa3055112.html

反転増幅回路と非反転増幅回路に周波数特性に違いがあるらしいのですがそれがどういった違いなのかわかりません。わかる方いらっしゃいましたら教えてください。 http://okwave.jp/qa4078817.html

関連する質問を紹介しますので、この回答を参考にレポートを書いてください。

μPC741というオペアンプを使って反転増幅の周波数特性をG=0,10,20dBと3種類測定しました。
(1)3種類とも利得が-3dBになる高域遮断周波数が約40kHzになりました。理論値と比較したいのですが理論式の導出がわからない
(2)周波数をあげると生じる入出力の位相差の原因とその理論式(たぶんスルーレートが関係すると思うのですが)
(3)位相差と利得の低下にはどんな関係があるのか http://okwave.jp/qa3510524.html

基本的な反転増...続きを読む

Q最長経路探索

グラフの最長経路(クリティカルパス)を求めたいのですが、
・閉路無し有向グラフ
・重み付きグラフ(辺ではなくノードの方に重みがある)
・スタートとゴールのノードが各々1つ与えられている
・スタートからどの経路を辿ってもゴールには辿り着く
以上のような条件の時に、どのようなアルゴリズムを用いれば良いのでしょうか?
幅優先探索で求められそうな気がしたのですが、どうも上手くいきません。
言語はVBAで、そもそも詳しくないのですが、
考え方など教えて頂けないでしょうか。
お願い致します。

Aベストアンサー

辺に重みのあるグラフを考えると, その上の最長経路問題は「辺の重みの正負をすべて入れ替えたグラフでの最短経路問題」になりますよね?
で, 得られたグラフには重みが負の辺もあるのでダイクストラ法は使えないんだけど, 閉路を持たないことは仮定されているのでベルマン・フォードを使えば最短経路 (= 元のグラフにおける最長経路) が分かります.

Qカットオフ周波数とは何ですか?

ウィキペディアに以下のように書いてました。

遮断周波数(しゃだんしゅうはすう)またはカットオフ周波数(英: Cutoff frequency)とは、物理学や電気工学におけるシステム応答の限界であり、それを超えると入力されたエネルギーは減衰したり反射したりする。典型例として次のような定義がある。
電子回路の遮断周波数: その周波数を越えると(あるいは下回ると)回路の利得が通常値の 3 dB 低下する。
導波管で伝送可能な最低周波数(あるいは最大波長)。
遮断周波数は、プラズマ振動にもあり、場の量子論における繰り込みに関連した概念にも用いられる。


ですがよくわかりません。
わかりやすく言うとどういったことなのですか?

Aベストアンサー

>電子回路の遮断周波数: その周波数を越えると(あるいは下回ると)回路の利得が通常値の 3 dB 低下する。
>導波管で伝送可能な最低周波数(あるいは最大波長)。
>遮断周波数は、プラズマ振動にもあり、場の量子論における繰り込みに関連した概念にも用いられる。

簡単にいうと、一口に「カットオフ周波数」と言っても分野によって意味が違う。
電子回路屋が「カットオフ周波数」と言うときと、導波管の設計屋さんが「カットオフ周波数」と言うとき
言葉こそ同じ「カットオフ周波数」でも、意味は違うって事です。



電子回路の遮断周波数の場合
-3dB はエネルギー量にして1/2である事を意味します。
つまり、-3dBなるカットオフ周波数とは

「エネルギーの半分以上が通過するといえる」

「エネルギーの半分以上が遮断されるといえる」
の境目です。

>カットオフ周波数は影響がないと考える周波数のことでよろしいでしょうか?
いいえ
例えば高い周波数を通すフィルタがあるとして、カットオフ周波数が1000Hzの場合
1010Hzだと51%通過
1000Hzだと50%通過
990Hzだと49%通過
というようなものをイメージすると解り易いかも。

>電子回路の遮断周波数: その周波数を越えると(あるいは下回ると)回路の利得が通常値の 3 dB 低下する。
>導波管で伝送可能な最低周波数(あるいは最大波長)。
>遮断周波数は、プラズマ振動にもあり、場の量子論における繰り込みに関連した概念にも用いられる。

簡単にいうと、一口に「カットオフ周波数」と言っても分野によって意味が違う。
電子回路屋が「カットオフ周波数」と言うときと、導波管の設計屋さんが「カットオフ周波数」と言うとき
言葉こそ同じ「カットオフ周波数」でも、意味は違うって事です...続きを読む

Q反転増幅器のカットオフ周波数の求め方

基本的な反転増幅回路における周波数特性が右下がりになる理由を理論的に説明したいのですが、回路にコンデンサが使われていないので、カットオフ周波数が求められなくて困っています。
オペアンプは751です。
右下がりになる理由はカットオフとオペアンプの周波数特性によるものですよね?



   

Aベストアンサー

式が少し違うところがありますが、Fcutは合っています。
V(t)=Asin(2πft)  Aは最大値(片振幅)
dV/dt=2πfAcos(2πft)  t=0のとき、[dV/dt]max=2πfA=SR
よって、f=SR/2πA (あなたの式には2が無い)
SR=0.5[V/μs] A=8[Vp0] とすると、f=0.5/2/3.14/8=0.020[MHz]=20[kHz] (あなたの計算結果と一致)
以上はあなたに従って最初から8Vで計算しましたが、電源電圧(例えば15V)で上限値を求めておくことも必要だと思います。

QオシロスコープのDCとAC

 まだ習いたてで、よく分かっていないのか、テキストの取り扱いの説明に、「AC/DCボタンを押すと直流・交流が入れ替わる」と書いてあるのですが、それは測る物によって選択するのですか? 乾電池は直流であるので、DCのモードにしておかないと測定できないということですか?

Aベストアンサー

通常はDCにして観測しますが、直流のオフセットがある信号を観測する場合はACにします。
たとえば、5Vの直流電圧に乗っている0.01Vのノイズ波形を観測したい場合、1V/divでは5Vであることはわかりますが、ノイズの波形は良くわかりません。
10mV/divにするとポジションをずらしても波形をみることができません。
このような場合、ACにして直流(5V)を除去すれば、ノイズ波形を詳しく観測できます。

Qマージソートの計算量について-O(n*logn)

マージソートの計算量はO(n*logn)ですが、なぜそうなのかが理解出来ません。要素数が2, 4, 8, 16, 32, 64...と増加すると二分割するのにかかる時間は1, 2, 3, 4, 5, 6..となり、n=2^x, x=lognとなるところまでは理解出来ました。しかし更にnをかける必要があるのはどうしてでしょうか。要素数が1になるまで分割した後に、小さい順番に比較しながら統合して行く作業があり、これにも当然ランニングタイムがかかるのはわかりますがなぜこの要素の比較コスト?が*nなのでしょうか。
またウェブで調べると、他にもT(n)=2T(2/n)+O(n)という別の説明もあり、こちらも理解出来ません。この説明は上の説明とはまた別の角度から説明しているものなのでしょうか。わかる人がいたら教えて下さい。

Aベストアンサー

ソートの計算量を議論するときは、通常「比較回数」を考えます。

(正確には、全ての計算の手間を数えあげる必要がありますが、通常
・計算処理の中で「比較回数」が最も多くなる
・計算量(オーダー)では次数の低い項は無視できる
ので、比較回数以外は考える必要がなくなります)

ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。


で、マージソートにおいて分割した部分列を統合するのにかかる時間ですが、
たとえば、16の要素をマージソートする場合を例にあげると、

・要素数が1の部分列を要素数が2の部分列に統合する時の比較回数は1回です。要素数が2の部分列は全部で8個あるので、比較回数は8回。

・要素数が2の部分列を要素数が4の部分列に統合する時の比較回数は3回です。要素数が4の部分列は全部で4個あるので、比較回数は12回。

・要素数が4の部分列を要素数が8の部分列に統合する時の比較回数は7回です。要素数が8の部分列は全部で2個あるので、比較回数は14回。

・要素数が8の部分列を要素数が16の列に統合する時の比較回数は15回です。要素数が16の列は全部で1個あるので、比較回数は15回。

以上合計すると、比較回数8+12+14+15=49回で64要素のマージソートができるわけです。

この「比較回数」を「要素数n」の式で表現するわけですが、
個々の部分列の統合時の比較回数は、要素数n、分割数kとすると、n-k回になりますから、n=2^x (x = log n) とすると、
総比較回数=Σ(k=0~x-1) (n-2^k) = n x - n + 1 = n log n - n + 1
になります。

計算量(オーダー)の議論では、次数の低い項は無視しますから、
O(n log n - n + 1) = O(n log n) になります。

ソートの計算量を議論するときは、通常「比較回数」を考えます。

(正確には、全ての計算の手間を数えあげる必要がありますが、通常
・計算処理の中で「比較回数」が最も多くなる
・計算量(オーダー)では次数の低い項は無視できる
ので、比較回数以外は考える必要がなくなります)

ですので、マージソートの計算量を考える場合、「分割にかかる時間」ではなく、「(比較しながら行う)分割した部分列を統合していくのにかかる時間」だけを考えます。


で、マージソートにおいて分割した部分列を統合する...続きを読む

Qボルテージフォロワの役割がよく分かりません。

ボルテージフォロワは、電流が流れることで寄生抵抗によって電圧値が低下しないようにするために、回路の入力段及び出力段に入れるものであると思いますが、
これを入れるのと入れないのでは具体的にどのような違いが表れるのでしょうか?

オペアンプを使った回路では通常、電流は流れないはずですので、このようなものは必要ないように思うのですが、どのような場合に必要になるのでしょうか?

Aベストアンサー

#1のものです。

ちょっと説明がうまくなかったようです。
ボルテージフォロワを使用するのは、次の段の入力インピーダンスが小さく電流がある程度流れる場合に、信号を元の電圧をそのまま受け渡す際に使用します。
とくに信号源の出力インピーダンスが大きいときは信号源に流れる電流を減らすため、受ける側の入力インピーダンスを大きくする必要があります。
反転増幅回路を用いると、入力インピーダンスを大きくすることができません。(反転増幅回路の入力インピーダンスは信号源と反転入力端子の間の抵抗にほぼ等しい。この抵抗の大きさはさほど大きくできない。)
非反転増幅回路を用いると、入力インピーダンスを大きくすることができます(非反転増幅回路の入力インピーダンスは非反転入力と反転入力のピン間インピーダンスにほぼ等しく、かなり大きな値になる。)が、増幅率が1よりも大きくなってしまいます。
これを元の信号のレベルに下げるために抵抗で分圧してしまうと、分圧に使用した抵抗分出力インピーダンスが増えてしまいます。これでは何のためにオペアンプを入れて電流の影響を減らしたの意味がなくなってしまいます。
元の電圧のまま、次の段に受け渡すにはボルテージフォロワがよいということになります。


次に、#1の補足に対して。
>反転増幅回路と非反転増幅回路は単に反転するかしないかの違いだと思っていたのですが、
>それ以外に特性が異なるのですか?
これは、上でも述べていますが、反転増幅回路と非反転増幅回路は、増幅回路の入力インピーダンスが異なります。
信号源の出力インピーダンスが大きく、電流が流れると電圧が変化してしまような用途では入力インピーダンスを高くできる非反転増幅が有利です。

>・出力インピーダンスとは出力端子とグラウンド間のインピーダンスだと思っていたのですが、それでいくと分圧するということは
>出力インピーダンスを下げることになるのではないのでしょうか?
違います。出力インピーダンスとは信号を発生させている元と入力先との間のインピーダンスを意味します。
出力インピーダンスは信号源から流れる電流による電圧降下の大きさを決定付けます。
オペアンプを使った回路での出力インピーダンスは、理想的な状態ですはゼロになります。
分圧用の抵抗を入れてしまうと、分圧に使用した抵抗のうち信号源と入力先に入っている抵抗分が出力インピーダンスとして寄与していしまいます。

>・それと非反転増幅回路の出力を抵抗などで分圧することで増幅率を1以上にするデメリットを教えて下さい。
これは、何かの勘違いですね。
非反転増幅回路で増幅率を1よりも大きくしたいのなら分圧などする必要はありません。
非反転増幅で増幅率を1以下にしたい場合は、何らかの方法で信号を減衰させる必要があります。ここで分圧を使うのはあまり好ましいことではないということです。

#1のものです。

ちょっと説明がうまくなかったようです。
ボルテージフォロワを使用するのは、次の段の入力インピーダンスが小さく電流がある程度流れる場合に、信号を元の電圧をそのまま受け渡す際に使用します。
とくに信号源の出力インピーダンスが大きいときは信号源に流れる電流を減らすため、受ける側の入力インピーダンスを大きくする必要があります。
反転増幅回路を用いると、入力インピーダンスを大きくすることができません。(反転増幅回路の入力インピーダンスは信号源と反転入力端子の間の抵抗...続きを読む


人気Q&Aランキング

おすすめ情報