私は最小ヒープと最大ヒープを研究しましたが、いくつか質問があります。
- ソートされた配列は最小ヒープですか？
- 最大ヒープの最小値はいくつですか？
40933 次
8 に答える
34
配列ベースのヒープ実装を使用する場合、最小から最大にソートされた配列は最小ヒープです。親ノードの値が子ノード（ゼロベースの配列を使用する場合は2i+1および2i+2）以下であるmin-heapプロパティは、子を持つすべてのノードに適用されます。
最大ヒープの最小値はリーフノードの1つにありますが、どちらかはわかりません。最小ノードは、定義上、子ノードを持つことができないため、リーフである必要があります。ただし、heapプロパティは、リーフノードが互いにどのように比較されるかを指定せず、親とのみ比較します。
于 2010-06-24T19:18:50.113 に答える
7
ソートされた配列は最小ヒープですか？
はい、一般的な配列格納ヒープ規則を使用している場合は可能です。
最大ヒープの最小値はどこにありますか？
葉の1つ。これは正確には未定義です。
于 2010-06-24T19:19:30.667 に答える
3
2 * i+1および2*i + 2（iは0から開始）と比較して、インデックスiの配列としてバイナリヒープを実装できます。最小ヒープでa[i]<a [2 * i+1]およびa[i]<a [2 * i + 2]
それで
1。ソートされた配列は最小ヒープです。
2。特定のインデックスはありません。それがただの葉であることを私たちが知っているすべて
このhttp://en.wikipedia.org/wiki/Binary_heapを読むことをお勧めします
于 2010-12-08T11:49:29.687 に答える
0
最大ヒープの最小値はどこにありますか？
回答：最大ヒープは、インデックスが1からnまでの単純な配列を使用して表すことができます。最初の要素は最大ヒープのルートです。ヒーププロパティ：インデックスiのノードは、2iに子を残し、2i + 1に右の子を持っています（2iと2i + 1がヒープサイズ、つまり配列の長さよりも小さい場合）。
最大ヒープのリーフノードは、インデックスi+1からnまで見つかります。ここでi=n / 2; nは配列の長さです。そして、リーフノードの1つに最小値があります。
したがって、a [i+1]からa[n]の値から最大ヒープの最小値を見つけることができます。最小値を見つけるための時間計算量はorder-of（ni）です。
于 2011-11-06T18:36:06.603 に答える
0
- ソートされた配列は最小ヒープですか？
昇順で並べられている場合（はい、一般的に言えば、最小ヒープ、より正確には） 、次のルールを使用したバイナリヒープの配列実装です。
- インデックスiのノードの子は、インデックス2i+1および2i+2にあります。
- インデックスiを持つノードの親は、インデックスフロア（（i-1）/ 2）にあります。
同時に、逆には機能しません。配列ベースのバイナリヒープは、並べ替えられたリストを格納しません。
- 最大ヒープの最小値はどこにありますか？
これは定義されておらず、キーを最小ヒープに格納するときにすばやく答えたい質問ではありません。O（1）時間でヒープの最小値と最大値の両方をピークできるようにしたい場合は、JavaのMinMaxPriorityQueueなどのクラスを使用できます。
于 2015-03-20T13:18:11.113 に答える
0
ソートされた配列は最小ヒープですか？
ソートされた配列はmin-heapまたはmax-heapのいずれかですが、その逆は真ではありません。min
-heapまたはmax-heapは必ずしもソートされた配列ではありません。
最大ヒープの最小値はいくつですか？
max-heap（または優先キュー）は、定義上、O（1）時間のコレクションから最大値を提供します。誰かが最大ヒープから最小値を取得する必要がある場合、この問題のために最初にヒープ自体を使用することは正しくありません。これは、スタックがFIFOアクセスを提供することを期待したり、キューがLIFOアクセスを提供することを期待したりするようなものです。
ただし、jfyi、最小値は、ヒープによって形成されたツリーの葉の1つになります。どのサブツリーにも存在する可能性があります。したがって、それを見つけるのにO（1）時間以上かかる別のアルゴリズムが必要です。
補足として：
n個の要素を持つヒープには、[1から（n + 1）/2]の葉がある場合があります。
ヒープによって形成される木の高さがhの場合、ヒープには最大2 ^（h-1）の葉があります。
于 2018-01-12T01:25:09.577 に答える
0
配列は、昇順または降順で並べ替えることができます。「ソートされた配列は最小ヒープです」というステートメントは部分的に正しいです。このステートメントの正しいバージョンは「昇順でソートされた配列は最小ヒープとして扱うことができます」であり、その補足ステートメントは「降順でソートされた配列は最大ヒープとして扱うことができます」です。
「昇順でソートされた配列は、最小ヒープとして扱うことができます」
ただし、「すべての最小ヒープが昇順でソートされた配列の形式をとることができるわけではない」ことを覚えておいてください。
そして、最大ヒープの最小値については、これが葉に存在することだけがわかっており、O（n）で検索できます。
于 2018-02-22T14:51:55.043 に答える
0
常に真実は：
昇順でソートされたリストはすべて最小ヒープです。
試してみてください。このルールにも例外はありません。
于 2022-01-15T15:38:22.153 に答える