意味わかんなくて笑う。笑 二分木ヒープで、木の高さをk, 要素数をnとすると2^(k-1)<= nの

意味わかんなくて笑う。笑
二分木ヒープで、木の高さをk, 要素数をnとすると2^(k-1)<= nの関係になるのでk<= n+1

とかいってますけど、
高さって深さの最大値で深さって根では0だから、深さnのとこまでの頂点数の総和って2^(n+1)-1でしょ？
だから下限は
k-1じゃなくてkで十分だと思うんですけどなんなんですか？

No.1 回答者： ありものがたり 回答日時： 2023/12/23 19:05

植木算って知らない？

この回答へのお礼

はい？？？？？

お礼日時：2023/12/23 22:14

No.2 回答者： Tacosan 回答日時： 2023/12/24 01:17

二分木ヒープだろうとなんだろうと, とにかく根付き木でありさえすれば

k≦n+1
は成り立つと思うんだ.

ところで「だから下限は
k-1じゃなくてkで十分だと思うんですけどなんなんですか？」
の「下限」って, いったい＊何の＊「下限」, なんだろうか. そして, 「十分」の根拠はなんなんだろう. いや, 「思う」のは勝手なんだが.

この回答へのお礼

日本語にがてですか？？

お礼日時：2023/12/24 08:38

No.3 回答者： mtrajcp 回答日時： 2023/12/24 05:20

深さkのとこまでの頂点数の総和

の最大値(上限)は
2^(k+1)-1
だけれども
下限ではない

No.4 回答者： mtrajcp 回答日時： 2023/12/24 05:46

深さkのとこまでの頂点数の総和

の最大値(上限)は
2^(k+1)-1
だけれども
下限ではない

左図では
深さk=3
要素数n=7
だから
2^k=8>7=n
2^k>n
だから
2^k≦nは成り立たない

この回答へのお礼

えとー、左は二分ヒープじゃないです。
二分ヒープの定義を見直してください。

お礼日時：2023/12/24 08:30

No.5 回答者： tknakamuri 回答日時： 2023/12/24 09:41

k<n+1は当然として

後の文章は意味不明。No.2に激しく同意。
読めると思っているのはあなただけでしょう。
色々推測するのはごめんこうむりたい(^_^;)

この回答へのお礼

お勉強してから回答してください。わからないことは調べてください。

お礼日時：2023/12/24 10:48

No.6 回答者： Tacosan 回答日時： 2023/12/24 09:56

「日本語が苦手か」と問われれば「日本語に限らず意思の疎通そのものが不得手だ」と答えてはおくけど, それはさておきふだんからそんな調子なんだとしたらあなたも相当だということを自覚すべきではなかろうか.

閑話休題.

で「下限」ってのはいったい何の「下限」なんだい? この質問文中「k-1」が出てくるのは (その部分を除くと) 「2^(k-1)<= n」の 1ヶ所しかないんだが, その「k-1」を「下限」と呼ぶことは常識でいってありえない.

だから聞いてるんだよ, 「下限」というのは何の「下限」のことなんだ, ってな.

この回答へのお礼

ごめんなさい、下限じゃなかったかもしれないけど、nを下から抑えるときに2^kで十分なのになんでk-1とかしてるんですか？ってきいてます。これ結局計算量がO(log2n)になるのいえればいいからそれで十分だしていうかn+1とかする意味なさすぎてバカ？って思います。

お礼日時：2023/12/24 10:52

No.7 回答者： mtrajcp 回答日時： 2023/12/24 10:16

深さkのとこまでの頂点数の総和

の最大値(上限)は
2^(k+1)-1
だけれども
下限ではないから
その理由からは
上限が2^(k+1)-1といえる
だけで
下限が(k-1)ではなくkであるとはいえないのです

No.8 ベストアンサー 回答者： Tacosan 回答日時： 2023/12/24 13:31

ふつうのヒープであればあなたのいう通りで, 高さ k のヒープに対しその頂点数 (要素数) n は

2^k ≦ n < 2^(k+1)
を満たす. もちろん「2^(k-1)<= n」も間違ってはいないけど 2^k ≦ n の方が「より厳密に評価している」という点において優れている.

なおどうして「2^(k-1)<= n」となっているのかは知らん. そのような表現をした者に聞いてくれ... というかこの質問自体もそっちに投げればよかったのでは?

この回答へのお礼

そですよねそですよね。ありがとございます。生計算の教科書に書いてあったんですけど、考えただけ時間無駄にしました。。。

お礼日時：2023/12/24 13:35