問題タブ [max-heap]

免責事項として、私はこのサイトを初めて使用するため、質問の仕方がよくわかりません。これらの概念のいくつかがどのように機能するかを理解しようとしているだけなので、あまり厳しくしないでください。最初の段階で理解できていない場合は、そこから始めて、残りの時間を無駄にしないように、そのことを教えてください。ここでは何も行きません。私の理解に問題があるのではないかと思うので、さまざまな領域でヒープがどのように機能するかについていくつか質問を投げかけ、それらに答えようとしました。

まず、空のヒープに追加されたランダムな数値のセットがどのように見えるかを理解する手助けをしたいと思います。たとえば、9、4、5、3、2、7、8、7 があるとします。それをヒープに追加した後、ヒープはどのようになりますか? これは視覚的に理解できます（と思います）9はルート、4は最初の左の子などですが、これは具体的にはツリーではなく、ヒープであるため、番号を切り替えてソートしますかそれらを（「私の理解が正しければ」の段落を参照）、最小または最大の順序でソートされるようにしますか？

ここで、ヒープから 9 を削除したとします (9 がルートになると思います)。この変更にどのように対応し、次に何がルートに入れられるのでしょうか? ここで、9 がルートの場合、次に大きい数字を取得して 9 のスロットにコピーしますが、これが最小ヒープであり、下部のノードを削除するだけの場合は、削除されるだけです。問題。

同様に、配列内のヒープ項目の親を取得する式は何になるでしょうか? -- これは理解できたと思います。親が i の場合、左の子は i*2 で右の子は i*2+1 になります。したがって、親を見つけるには、親を見つけるために i/2 を割る必要があります。たとえば、i=7 の場合、親は i=3 になります。これは、3.5 が切り捨てられるためです。また、i=6 の場合、親も i=3 になります。この例から、i = 7 の子は i = 3 の右の子になり、i=6 は i = 3 の左の子になります。

これについての私の理解が正しければ、新しい用語がルートに追加された後に再ヒープするには、子を親と比較し、子が大きい場合は用語を切り替えます。しかし、2 つの子 (2 つある場合) を比較して、どちらが大きいかを確認し、どちらを交換する必要があるかを判断する必要があります。これは最大ヒープの場合であり、最小ヒープの場合は逆になります。

最後に、ルート要素をどこに追加するとしたら、どのように再ヒープするのでしょうか?

私はヒープソートを学ぼうとしています。疑似コードの指示に従いますが、プログラムが正しく動作しません。私はすでに1時間デバッグしていますが、バグを見つけることができませんでした. いくつかのバグがあります。まず、arraylist が正しくソートされません。第 2 に、配列リストは、最小 -> 最大であると想定されているにもかかわらず、最大 -> 最小でソートされているように見えます。初歩的な質問ですみません。

Python で max-heap データ構造を使用してプライオリティ キューを実装しています。優先順位として関連付けられた番号を持ついくつかの名前を使用しています (9 が最高で 1 が最低です)。私が直面している問題は、優先度キューからアイテムをデキューするときに、優先度が最も高いアイテムをデキューしないことです。これは、エンキューに問題があり、優先度に基づいてアイテムをヒープ内の正しい位置に挿入していないことを意味すると思います。誰かがこれを修正するのを手伝ってくれるなら、それは大歓迎です。

私の優先キューコード:

コードを実行して main を呼び出した後の出力:

最大ヒープ コード (教科書で提供):

Go に慣れるために、練習用に最大ヒープを実装しようとしています。

[4,1,3,2,16,9,10,14,8,7]I Produceの配列について[16 14 9 10 8 1 4 2 3 7]

9 は 1 レベル高すぎて、10 に切り替える必要があるため、これは間違っています。

どこが間違っていますか？

また、ヒープソートを試みると、何かがおかしいことも知っています

それは動作しません。

2 つの最大ヒープをマージする最も効率的なアルゴリズムを見つける必要があります。

いくつかの重要な事実: ヒープはバイナリ ツリーとして表されます。つまり、各ノードには 3 つのフィールド (値 (キー)、右の子へのポインター、左の子へのポインター) があります。

私の考え: 2 番目のヒープの最後の葉を取り、それを新しいヒープのルートとして配置します。したがって、左側の子が正当な最大ヒープであり、右側の子が正当な最大ヒープである場合、新しいヒープを取得します。(私の意見では) 問題は、ルートが最大要素ではないという事実だけです。そのため、ルートから関数Max-Heapifyを実行でき、問題を解決できると思います。

最悪の場合の総実行時間 - O(logn) - リーフをルートとして作成するのはO(1)であり、Max-HeapifyはO(logn)であるためです。

あなたはそれについてどう思いますか？私は正しいですか？2つの最大ヒープをマージするためのより効率的なアルゴリズムはありますか? (表現が二分木であることを考慮してください)

この Priority Queue の実装では、再帰を使用して、メソッドのパラメーターとして受け取る配列がIsMaxHeap最大ヒープかどうかを判断する必要があります。

これが機能するか、または問題なく機能する可能性があるすべてのケースを確実に評価したいと思います。

私たちを手伝ってくれますか？