問題タブ [min-heap]

min-heap を使用して heapSort を実装していますが、350 要素以下で正常にソートされます。配列が約 350 要素になると、正しく並べ替えられません。エラーがどこにあるかはわかりませんが、extractMin()、または再帰に関係していると思われます。クラス全体minHeapを徹底的に追加し、バグが他の場所にないことを確認しました。

これが私のコードです：

クラスから始めminHeapます：

ここにextractMin（まだminHeapクラスの一部）があり、これが原因である可能性があります：

関数 (クラスheapSortに関連付けられていない) :minHeap

私のメイン：

私が得る出力：

特定の .txt ファイルからテキストを読み取る必要がある C++ プログラムがあるとします。プログラムは次のことを行います。

• ファイル内の各文字の出現回数を計算すると、一意の各文字（およびその頻度）が新しいツリーノードとして保存されます
• 次に、プログラムはこれらのノードを含む最小ヒープを構築し、この最小ヒープを使用してハフマン コード ツリーを構築します。
• トラバーサル (事前順および順序順) が出力ファイルに書き込まれます。ツリーの各内部ノードには I:xxx というラベルが付けられます。ここで、xxx は int ラベルであり、葉には L:xxx が付けられます。
• プログラムは最終的に、文字列として格納された各文字のエンコーディング (ASCII ベースであり、真の .bin バージョンではありません) を含むテーブルを作成します。

次のように、各ノードをハフマン クラス内に格納するとします。

どこに進むべきか正確にはわかりません。どんな助けでも大歓迎です！

組み込みのヒープ関数を使用せずに、Python で完全な MIN-HEAP 実装を構築する必要があります。

したがって、0 からの python 番号リスト要素を考慮した、親、左の子、および右の子の定義があります。

次に、（疑似）ランダムリストをリストlに生成するコードの一部があります。

そして、この時点まではすべてうまくいきます。次に、テーブルlを最小ヒープにする関数 bkop があります。

次に、プログラムを実行して結果を確認します。

######### でマークした 3 行を指す範囲外のエラー リスト インデックスでプログラムがクラッシュします。私は約 1 か月前にこれを書き始めましたが、確かにその親、lchild、rchild は当時働いていました。何が悪いのかわかりますか？

EDIT1: 親/子/子の定義を修正しました。確認しましたが、正しい値が返されます。コードは次のとおりです。

ランダム リストを生成する関数はほとんどそのままです。次に、この bkop 関数があります ( lリストから最小ヒープを作成します)。意図的に前後に print を使用して、機能するかどうかを確認します...そして機能しません。どちらも同じリストを返し、コンパイルエラーなどはありません。それを修正する方法はありますか？

EDIT2：わかりましたので、あなたが提案したようにbkopを修正しました：

しかし、それを実行すると、最初にランダムに生成されたテーブルが取得され (当然のことですが)、最小ヒープ テーブルの代わりに、以下のようにNone値が取得されます。

何か案は？l[i] を親と比較するのではなく、l[i] を左右の子と比較するのではなく、別の方法で行う必要がありますか?

こんにちは、javascript で最小ヒープを実装しようとしましたが、最小値を削除するためのアルゴリズムについて質問がありました。内部でヒープを表すために配列を使用しています。下に浸透している場合、停止条件はどうすればよいですか? 私のコードでは、 2 * k <= this.size にあるので、最後の要素まで移動する可能性がありますが、「正しい」とは感じません。より良い停止条件はありますか? 前もって感謝します！

最小ヒープの形式で配列を表現しようとしています。そして、親が右の子よりも大きい (12 より大きい 6) リーフ ノードの 1 つで問題に直面しています。コーディングの何が問題なのか理解できません。助けてください。

これが私のコードです：

私が得ている出力は次のとおりです。

昨日質問したのですが、よく分からなかったので、具体的な質問です。

最小ヒープを配列として表しています。私はminheapsについてよく理解していると思いますが、その中の特定の概念については曖昧です。最小ヒープは、常にルートとして最小のノードを持つことになっています。値を削除するには、ルートを配列表現 (リーフ ノード) の最後の要素に設定し、配列のサイズを減らします。次に、siftDown/PercolateDown または任意の名前を使用して、ルート ノードを正しく配置します。これは超効率的です。例えば：

ここでは、最後の要素から 29 が取得され、siftDown(1) によって配置されます。

1. 29 を 15 および 38 と比較します。29 と 15 を交換します。
2. 29 は 25 および 20 と比較されます。29 と 20 を交換します。
3. 29 は 30 と比較され、29 < 30 であるため、これで完了です。

これで問題ありませんが、最小値を削除する 2 つのインスタンスの間に、他のデータの一部が変更された場合はどうなるでしょうか。例えば：

ここでは、次のようにします。

1. 29 を 15 および 38 と比較します。29 と 15 を交換します。
2. 29 は 30 および 32 と比較されます。29 < 30 および 29 < 32 したがって、完了です。

1 はツリーの最小値ですが、最小値として設定されておらず、15 が設定されています。これは私にとって大きな問題です。Dijkstras アルゴリズムを実装しようとしています。Java 組み込みクラスに触れずに独自のデータ構造を使用しようとしています。

したがって、私の問題に関連するより適切な例は次のとおりです。

Dijkstras に精通している場合、99 は暫定的な無限距離を表し、その他の数字は次にアクセスする必要があるグラフ ノード (最小距離のノード、この場合は 3) を表します。

解決策は、min を削除するたびにツリーを再構築することですが、これは minheap の能力が失われ、実装が遅くなることを意味します。

これを正しく理解していない場合は申し訳ありませんが、何日もこれに悩まされており、本当に助けが必要です.

サイズ k の minHeap を実装しようとしています。

min-heap のプロパティは作成された配列内に維持されますが、値は正しくありません。

例=> k=5; 入力: 5,3,9,6,13,1 ; 出力は次のとおりです: 1 3 5 6 13 正しい出力は 3,5,6,9,13 である必要があります

私のコード:

たとえば、整数の MinHeap があります。ヒープの途中からいくつかの値を増やしても、ソートされたヒープを正しく保存する方法があるかどうかを尋ねたいと思います。

ありがとう