問題タブ [heap]

^{1から始まるインデックスが付けられた2m} -1の異なる比較可能な要素の配列が与えられます。

配列を完全な二分木として見ることができます。

たとえば、アレイ

[7 6 4 5 2 3 1]

木です

バイナリツリーとして表示すると、これらの要素はヒーププロパティを満たし、ノードはその両方の子よりも大きくなります。

A[i] > A[2i] and A[i] > A[2i+1]

結果のバイナリツリー（上記のとおり）がバイナリ検索ツリーになるように、配列の要素をシャッフルするための適度に高速なインプレースアルゴリズムはありますか？

二分探索木では、ノードはすべての左の子孫よりも大きく、すべての右の子孫よりも小さいことを思い出してください。

たとえば、上記の配列の再シャッフルは次のようになります。

[4 2 6 1 3 5 7]

これは二分探索木に対応します

だから、ここでbottomupheapアルゴリズムを実装しようとしています: http://www.apl.jhu.edu/Classes/Notes/Felikson/courses/605202/lectures/L8/L8.html

Javaでプログラミングしてからしばらく経ちましたが、不明なエラーが発生し続けています。アルゴリズムのステップのいくつかを片付けて、誰かが私を助けてくれるかどうか疑問に思っていました.

データと左右の参照ポインター (または Java がそれらを呼び出すもの) を使用してヒープ ノードを作成しました。入力シーケンスは、に変換される配列ですArrayList。それが上記の関数に渡すものです。

S から最初のキーを削除し、そのキーで新しいノードを作成します。私の例では、Integers を使用しているだけで、キーはデータ参照に設定されています。

私はそれから使用 S1 = S.sublist(0, S.length/2) し、 S2 = S.sublist(S.length/2, S.length)

ここで、H1 と H2 はヒープまたはノードであると仮定しますか? ここで、Java で何をすべきかについて少し混乱します。

次に、次の部分については、そうする必要があるように見えますk.left = H1。k.right = H2

「k at root」と表示されるタイミングがよくわかりません。kルート ノードではありませんか。その場合、ダウンヒープ バブルkも同様に実行しますか? では、最後はこの時点でもH？k

投稿するコードがないのは残念ですが、エラーは再帰呼び出しのサブリストにあります。

更新しました：

AnArrayListは S として渡されます。Treeは として定義されTree(data, left, right)ます。ありがとう。

ありがとう！

ここで質問するのは初めてです。正式な手順を破らないように最善を尽くします。

Mark Allen Weiss バイナリ ヒープ コード ( http : //users.cis.fiu.edu/~weiss/dsaajava2/code/BinaryHeap.java) で、コードはほぼ完成しています。ただし、ヒープをテストするときに問題があるようです。テスト ケースが無限ループに入り、その理由がわかりません。問題の解決にご協力いただければ幸いです。

テストケースの関連部分は次のとおりです（「ヒープ」は3ヒープです）：

そして、ここに私のコードがあります:

だから、ここでbottomupheapアルゴリズムを実装しようとしています: http://www.apl.jhu.edu/Classes/Notes/Felikson/courses/605202/lectures/L8/L8.html

Javaでプログラミングしてからしばらく経ちましたが、不明なエラーが発生し続けています。アルゴリズムのステップのいくつかを片付けて、誰かが私を助けてくれるかどうか疑問に思っていました.

データと左右の参照ポインター (または Java がそれらを呼び出すもの) を使用してヒープ ノードを作成しました。入力シーケンスは、に変換される配列ですArrayList。それが上記の関数に渡すものです。

S から最初のキーを削除し、そのキーで新しいノードを作成します。私の例では、Integers を使用しているだけで、キーはデータ参照に設定されています。

私はそれから使用 S1 = S.sublist(0, S.length/2) し、 S2 = S.sublist(S.length/2, S.length)

私がこれまでに持っているものは次のとおりです。

AnArrayListは S として渡されます。Treeは として定義されTree(data, left, right)ます。ありがとう。

空のリストが渡されると、何らかの理由でサブリストを使用するときに空のリストとは見なされないようです。S.isEmpty() などの空で何かをしようとすると、エラーがスローされるようです。

ありがとう！

複雑さが 3*N になるような C++ の make_heap のアルゴリズムは何ですか? 要素を挿入してヒープを作成する唯一の方法は、O(N Log N) の複雑さです。どうもありがとう！

私はこれを数日間理解しようとしています。私は次のように言う学校の問題を抱えています：

Aを最小ヒープとします。操作HEAP-MODIFY（A、i、k）は、ノードiのキーを新しい値kに変更してから、最小ヒープ内の要素を再配置します。n要素の最小ヒープに対してO（lgn）時間で実行されるHEAPMODIFYの実装を提供します。

O（lg（n））時間で実行されるアルゴリズムを設計する必要があるため、各要素を反復処理するだけでは不十分であることがわかります。私は次の解決策を持っていますが、それが正しいかどうかはわかりません。

これにどのように取り組むことができるかについての提案はありますか？

これが私のシナリオです。線形時間の分や操作に頼ることなく、A *（Pythonで）を実装したいと思います。最小重量のアイテムを効率的に取得できるようにするには、ヒープが必要です。

私の即時の応答は'簡単でした！heapqを使用します！」それから私は、人生が私たちが望むほど単純であることはめったにないことを発見しました。この戦略は、A*の重要なポイントの1つにとって最適ではないことがわかりました。子供を考えるとき、私は時々、すでにヒープ上にある子供たちのスコアを更新する必要があります。

A *の記憶が少しなくなった人にとって、その要点は、要素を取得し、その重みを変更し、変更を反映するようにヒープを変更することです。これらはすべて劣線形時間で行われます。

助言がありますか？

二分木で作られたヒープがあります。配列ではありません。これをどのように並べ替えればよいか、考えてみました。最後のノードを取得してルートに配置し、ダウン ヒープ バブルを実行する必要があることはわかっています。私が持っているこの部分。私が抱えている問題は、新しい最後のノードを取得する方法を知っていることです。最後のノードを見つけるアルゴリズムはありますか? 各ノードの各親ノードを追跡する必要がありますか?

ありがとう。

私はヒープに関するいくつかの宿題に取り組んでおり、ヒープがどのように構造化されているかを理解しています。ヒープには、ヒープ プロパティを満たす各ノードが必要です。

max-heap プロパティは、ルート以外のすべてのノード i について、Heap[Parent(i)] >= Heap[i] です。

したがって、各ノードでは、上位のノードほど数値が高くなり、下位のノードほど数値が低くなります。これは分かります。しかし、リスト内の最大のn個の数値を単純に取得する以外にヒープを使用する方法は見当たりません。特定の値を検索してノードを返したり、(最大ヒープ内で) n 個の最小値を検索したりする簡単な方法がわかりません。どちらも、二分探索木では比較的簡単です。

単純な二分探索木を使用しないのはなぜですか? それとも、バランスの取れた二分探索木ですか?

編集：これは宿題の問題に対する答えを探しているわけではないことに注意してください。実際の課題は、insert() 関数と extractMax() 関数の並列 p ヒープの疑似コードを作成することでした。そして、私はすでにそれらに答えました。彼らは私がヒープを本当に理解していないことに気づきました。