問題タブ [binary-heap]

Node*module にある s のヒープに対して次のコードを作成しましたnode。

次に、次の単体テストを実行してみました。ここでは、指定された引数で初期化されたをmake_leaf返します。Node*

テストは、コメント マークを付けた行に到達し、その行enforce(a && b)で強制エラーをスローしcmp_node_ptrます。なぜこれが起こっているのか、私は完全に迷っています。

n 値を指定して、Binary Max-Heap を作成しました。任意の位置 i を根とする部分木の高さを計算する式を知りたいです。

二項ヒープにいくつかの値を挿入する必要があります。たとえば、25、26、24、60、65、62 です。次のようになります。

しかし、同じヒープに 25、68、65 を挿入する必要があります。25 を再度挿入するか、ヒープに既に存在するためスキップする必要がありますか?

MAX-HAPIFY(A,i) メソッドは、アルゴリズム入門の本から書きました。今度はwhileループを使って再帰なしで書きたいと思います。助けてください。

ヒープ データ構造を理解するために、独自のヒープ モジュールを実装しています。それらがどのように機能し、管理されているかは理解していますが、私の実装は、ヒープソートを実行している間、標準の python heapq モジュールよりも大幅に遅くなります (サイズ 100,000 のリストの場合、heapq は 0.6 秒かかりますが、私のコードは 2 秒かかります (元は 2.6 秒でした)。 percDown から len() ステートメントを取り出して長さを渡すことで 2 秒まで短縮できるため、メソッドがそれ自体を呼び出すたびに len を計算する必要がありません) これが私の実装です。

popMin: 最小値 (lst[0]) をポップし、ヒープを並べ替えます

heapify: リストをその場でヒープに変換します

sort: 上記のメソッドを使用して、指定されたリストをヒープソートします (インプレースではありません)。

アルゴリズム/ヒープの作成に誤って複雑さを追加しましたか、それとも python heapq モジュールが大幅に最適化されているだけですか? 0.6 秒と 2 秒では大きな違いがあるので、前者だと思います。

Weiss の「Data Structures and Algorithms In Java」では、バイナリ ヒープの挿入アルゴリズムについて次のように説明しています。

穴をツリーの上に移動するという原則は理解できますが、for ループでこの構文を使用して彼がそれをどのように達成しているのか理解できません... 初期化子のarray[0] = x;意味は何ですか? 彼はルート値を上書きしているようですか？非常に不自然なコードのようです。彼は何をしているのですか？