配列にデータを格納している MinMax Heap の実装がたくさん見つかりました。それは私が何か違うものを探している方法です。左の子と右の子へのポインター (および比較するキー) を持つヒープの要素のみを使用して、MinMax ヒープを作成したいと考えています。したがって、ヒープにはルート オブジェクト (最小レベル) へのポインターのみがあり、ルート オブジェクトにはその子へのポインター (最大レベル) などがあります。新しいオブジェクトを挿入する方法は知っていますが (ヒープ サイズに応じて int のバイナリ表現を使用して適切なパスを見つける)、残りを実装する方法はわかりません (要素を押し上げ (押し下げ)、親または祖父母を見つけます)。 .
助けてくれてありがとう
ヒープ順バイナリ ツリーを使用するプライオリティ キューは、配列の代わりに三重リンク リスト構造を使用して実装できます。ノードごとに 3 つのリンクが必要になります。2 つが下方向に、1 つが上方向にトラバースします。
heapqモジュールのソースコードは、プッシュアップとプッシュダウンの手順を実装することを示しています。配列の実装からポインターの実装に切り替えるには、arr[2*n+1]計算をnode.leftとarr[2*n+2]に置き換えnode.rightます。などの親参照のarr[(n-1)>>1]場合、すべてのノードにはその親へのポインタが必要node.parentです。
または、これをすべて非常に簡単に実装できる機能的なスタイルを採用することもできます。Lispに実装されたtreapのコードは、これを行う方法のインスピレーションであることがわかりました。
私はずっと前に割り当ての一部としてこの問題を解決しました。ここで見つけることができます
私は Java と C++ で複数の実装を行っており、配列の有無にかかわらず MinHeap を実装しています。解決策については、私の Java 実装を参照してください。はい、配列なしでヒープを実装することは非常に可能です。次のノードを挿入する場所と、ヒープ化および逆ヒープ化の方法を覚えておく必要があります。
Edit1:配列のない最小ヒープの既存のソリューションも検索しようとしましたが、見つかりませんでした。そのため、ここに投稿して、アプローチを知りたい人に役立つようにします。
配列なしでバイナリヒープを実装するのは難しいです。挿入中にすべての親を保持する必要があるため、パスしてからプッシュアップとダウンの操作を行います。そのように[parent_1, parent_2 ... parant_k] and then if parent_(k+1) < parant_k pushUp、右の子と左の子を並べ替えます