データを配列に格納していたMinMax Heap実装が多数見つかりました。実現するのは本当に簡単です。つまり、私は別のものを探しています。ヒープの要素だけを使用して、左の子と右の子へのポインタを使用してMinMaxヒープを作成したい（そして、比較するためにキーを辿る）。そのため、ヒープにはルートオブジェクト（最小レベル）へのポインタのみがあり、ルートオブジェクトにはその子（最大レベル）へのポインタなどがあります。私は新しいオブジェクトを挿入する方法を知っている（ヒープサイズに応じてintのバイナリrepresenationを使用して適切なパスを見つける）が、私は残りの部分を実装する方法を知らない（要素を押し上げる、親または祖父母を見つける） 。配列のないMinMaxヒープ実装
助けを借りて
配列のないバイナリヒープを実装するのは難しいです。あなたがパスを挿入している間、あなたはすべての親を保持する必要がありますし、操作を上下に押してください。そのような[parent_1, parent_2 ... parant_k] and then if parent_(k+1) < parant_k pushUpとその右の子と左の子供を並べ替える
heapq module source codeは、上下に押し上げるためのステップを実装することを示しています。配列の実装からポインタの実装に切り替えるには、node.leftとarr[2*n+2]をnode.rightに置き換えてarr[2*n+1]を置き換えます。 arr[(n-1)>>1]のような親参照の場合、すべてのノードはその親へのポインタnode.parentを必要とします。
また、これをすべて実装するのが簡単な機能スタイルを採用することもできます。私はtreaps implemented in Lispのコードがこれを行う方法のインスピレーションであることを発見しました。
少なくとも明らかではないことの1つは、heapushのheap.append（item）の翻訳方法です。これを実装するには、最後のアイテムへのポインタを維持し、新しいアイテムを追加するための適切な親を見つけるためにいくつかの（単純な）ツリートラバースを行う必要があります。 heappopは対称的な問題を抱えています。問題は 'last'ポインタを適切に更新することです。 –
ヒープ順序付きバイナリツリーを使用する優先度キューは、配列の代わりにトリプルリンクリスト構造を使用して実装できます。ノードごとに3つのリンクが必要になります.2つは横断し、もう1つは横断します。
申し訳ありませんが、これはまったく役に立ちません。私はそれが可能であるかどうか、そして単純な解決法（アルゴリズム）を知る必要があります。 – user1071076
これは問題の解決ではありません。 – briantaurostack7