問題タブ [heap]

ヒープに挿入する場所をどのように追跡しますか: 各サブツリーの高さをチェックする関数を使用すると、アルゴリズムが O(log N) から O(N) に低下すると思います。

各ノードに変数を保持するか、最後の挿入スポットを持つヒープに変数を保持しますか(どのように定義されていますか?)。

この関数に関するドキュメントが見つかりませんでした...

私は特にパラメータが何であるか、そしてパラメータが正確に何を表しているのか知りたいです...

Python3を使用する

私はヒープソートを実装する方法を学ぼうとしてきました。

特に、入力を昇順でソートするヒープソートアルゴリズムがありますが、降順にするために何を変更する必要があるのか​​わかりません。

コードは次のとおりです:(これの一部は教科書からのものです）

コードのどの部分を変更する必要があるかを誰かが指摘できれば、それは非常に役立ちます:)。

次のように PriorityQueue を使用してヒープを実装しようとしています。

上記のメソッドを保持する同じクラス内のプライベート クラスとして Node を定義した場所。ノードは次のように定義されます。

ただし、ノードを PriorityQueue に追加すると、それらは頻度順に並べられません。私のprintlnステートメントからの出力に基づいて、Node.compareTo()によって正しい値が返されます。たとえば、次のデータセットがあるとします。

• 名前、頻度
• 必要、3
• 猫、1
• ニート、2

私のコードは次のように生成します:
// need
[need]を追加します
// cat
cat < need
[cat, need]を追加します
// きちんとしたニートを追加し
ます > cat
[cat、need、neat] PriorityQueue
が [cat、きちんと、必要]
なぜこれが起こっているのかについてのヒントは？

だから私はバイナリ最小ヒープを実装しようとしています。バイナリ最小ヒープがその構造とプロパティに関して何を伴うかを理解しています。ただし、ポインターとノードを使用して実装しようとすると、壁にぶつかります。

、およびを使用してNodeいます。挿入された最後のノードを指す場所もあります。right/left and pointersint elementparent pointerLastNode

私の口論は、最後のノードに関して、要素を挿入するときに何をすべきかわからないということです。これが私の言いたいことです。

ステップ 1.) ヒープが空であると仮定します。rootつまり、x に要素が含まれる x を作成し、 および を設定root.left/right = nullしLastNode = root.leftます。

これは私が立ち往生している部分です。別の要素を格納するために別のノードを作成すると、それは X の左側または LastNode が指す場所になることを私は知っています。私の質問 LastNode で次に何をすればよいですか? x.right を指すようにしますか? 私はinsert(int x)logN で実行し続けようとしています。lastNode の操作は、各レベルでより長く、より広範囲になります。

誰かがそれを分解できますか？ありがとう

Javaで効率的な優先キューを実装しようとしています。バイナリヒープの適切な実装に到達しましたが、理想的なキャッシュパフォーマンスがありません。このために、私はバイナリヒープでVan Emde Boasレイアウトの調査を開始しました。これにより、バイナリヒープの「ブロック」バージョンが作成されました。ここでの秘訣は、子と親のインデックスを計算することです。

これはできましたが、キャッシュの動作（および実行時間）が悪化しました。問題は次のとおりだと思います。Javaであるため、参照の局所性が達成されていない可能性があります。オブジェクトの配列を使用すると、実際にオブジェクトがJavaのメモリ内で連続するかどうかはわかりませんが、誰かがこれを確認できますか？

また、JavaのネイティブPriorityQueueがどのようなデータ構造を使用しているのかを知りたいと思います。

ヒープからランダムノードを削除したいという状況がありますが、どのような選択肢がありますか？ヒープの最後のノードと最初のノードを簡単に削除できることはわかっています。ただし、最後のノードを削除すると言うと、ヒープからランダムノードを削除するための動作が正しく定義されているかどうかはわかりません。

例えば

したがって、この場合、ノード12と22を削除できますが、これは定義されていますが、たとえば、ランダムノード（たとえば13）を削除しても、ヒープの完全なツリープロパティを（他のプロパティとともに）維持できますか？

http://www.cplusplus.com/reference/algorithm/make_heap/

このリンクで。それは言う：

内部的には、ヒープは、各ノードがそれ自体の値以下の値にリンクするツリーです。make_heapによって生成されたヒープでは、メモリを消費するリンクによって決定されるのではなく、ツリー内の要素の特定の位置がシーケンス内の絶対位置によって決定されます。*firstは常にヒープ内の最大値です。

約「シーケンス内の絶対位置によって決定されます」。私はここで混乱しました。また、「ヒープは、各ノードがそれ自体の値以下の値にリンクするツリーです」とも書かれています。

それらの2つの文は矛盾していますか？ここでとても混乱しています。C ++のヒープのツリーとは正確には何ですか？

親切な人が私を助けてくれることを願っていますどうもありがとう

重複の可能性：
バイナリ最小ヒープのリンクリストの実装（操作に問題があります…）

ご挨拶、

バイナリヒープのリンクリスト実装でツリーノードの場所を取得するアルゴリズムを理解するのに問題があります。配列を使用してヒープを実装しました。リンクリストを使用してみます。ヒープを表すために配列を使用した場合、配列インデックスがあったツリーノードを見つける方法はありますか？

私のデータ構造クラスの宿題は、汎用ヒープ ADT を作成することです。siftUp() メソッドでは比較を行う必要があり、親が小さい場合はスワップを行う必要があります。私が抱えている問題は、ジェネリック型では比較演算子が有効でないことです。Comparable インターフェースを使用する必要があると思いますが、私が読んだことから、配列で使用するのは良い考えではありません。このサイトも検索しましたが、この投稿に関連する良い情報を見つけましたが、解決策を見つけるのに役立ちませんでした

関係のないコードの一部を削除しました ありがとう