問題タブ [binary-heap]

ウィキペディアを引用：

従来のバイナリ ツリー データ構造を使用してバイナリ ヒープを実装することはまったく問題ありません。アルゴリズムで解決 できる要素を追加するときに、バイナリ ヒープの最後のレベルで隣接する要素を見つけることに問題があります...

そのようなアルゴリズムがどのように機能するかについてのアイデアはありますか?

ほとんどのバイナリ ヒープは配列を使用して実装されているため、この問題に関する情報は見つかりませんでした。

どんな助けでも感謝します。

最近、OpenID アカウントを登録しましたが、最初の投稿やコメントの回答を編集できません。そのため、この回答で回答しています。申し訳ありません。

ミッチ・ウィートの引用：

@Yse：「バイナリヒープの最後の要素を見つけるにはどうすればよいですか」という質問はありますか？

はい、そうです。または、より正確に言うと、私の質問は、「非配列ベースのバイナリ ヒープの最後の要素を見つけるにはどうすればよいですか?」です。

Suppressingfire の引用:

この質問をしている文脈はありますか？(つまり、解決しようとしている具体的な問題はありますか?)

上記のとおり、ノードの挿入と削除に必要な「非配列ベースのバイナリヒープの最後の要素を見つける」ための良い方法を知りたいです。

ロイの引用：

通常のバイナリ ツリー構造 ([data, pLeftChild, pRightChild] として定義された pRoot と Node を使用) を使用し、2 つの追加ポインター (pInsertionNode と pLastNode) を追加するのが最も理解しやすいようです。pInsertionNode と pLastNode は両方とも、挿入サブルーチンと削除サブルーチン中に更新され、構造内のデータが変更されたときにそれらを最新の状態に保ちます。これにより、構造体の挿入ポイントと最後のノードの両方に O(1) アクセスできます。

はい、これでうまくいくはずです。私が間違っていなければ、削除/挿入のために場所が別のサブツリーに変更されたときに、挿入ノードと最後のノードを見つけるのが少し難しいかもしれません。しかし、私はこれを試してみます。

ザック・スクリヴェナの引用:

深さ優先検索を実行するのはどうですか...

はい、これは良いアプローチです。私もそれを試してみます。

それでも、最後のノードと挿入ポイントの位置を「計算」する方法があるかどうか疑問に思っています。N 個のノードを持つバイナリ ヒープの高さは、N よりも大きい最小の 2 のべき乗の (2 を底とする) 対数を取ることで計算できます。おそらく、最も深いレベルのノード数も計算できます。次に、挿入ポイントまたは削除用のノードに到達するためにヒープをどのようにトラバースする必要があるかを判断することができた可能性があります。

基本的に、バイナリ ヒープとリニア プロービング ハッシュテーブルをマージして、ヒープの機能とハッシュテーブルの並べ替え機能を備えた「複合」データ構造を作成する必要があります。

私がする必要があるのは、データ構造 (バイナリ ヒープとハッシュ) ごとに 2 つの 2 次元配列を作成し、ポインターを使用してそれらを相互にリンクし、バイナリ ヒープの値を削除するなどの変更を行うと、それも取得されるようにすることです。ハッシュ テーブルから削除されます。

したがって、ヒープから Hastable を指すヒープ配列の 1 行と、ハッシュテーブルからヒープを指すハッシュテーブル配列の 1 行が必要です。

Haskell の演習として、ヒープソートを実装しようとしています。ヒープは通常、命令型言語では配列として実装されますが、これは純粋な関数型言語では非常に非効率的です。そこで私はバイナリ ヒープを調べましたが、これまでに見つけたものはすべて命令的な観点からそれらを説明しており、提示されたアルゴリズムは機能的な設定に変換するのが困難です。Haskell などの純粋関数型言語でヒープを効率的に実装する方法は?

編集:効率的とは、まだ O(n*log n) である必要があることを意味しますが、C プログラムに勝る必要はありません。また、純粋に関数型プログラミングを使用したいと思います。Haskellでそれを行うことのポイントは何ですか?

私はしばらくの間質問に悩まされていて、誰かが私を正しい方向に向けることができるかどうか疑問に思っていました：

バイナリヒープが、配列ではなくポインタベースのツリー表現を使用して表されているとします。バイナリヒープLHSをRHSとマージする問題を考えてみましょう。両方のヒープが完全な完全なツリーであり、それぞれ（2 ^ L -1）ノードと（2 ^ R -1）ノードを含むと仮定します。
2つのO（log N）アルゴリズムを指定して、2つのヒープをマージします。1つはL = Rの場合、もう1つは| L--R|の場合です。=1。

これは宿題の問題です。正しい方向に向ける必要があります。

この minheap コードについて助けが必要です:

このコードは、画面上の最後の要素をポップするときに乱数を出力することを除いて、ほとんどすべてを正しく実行します。あなたの意見は何ですか？

ありがとう！

たとえば、max-heap で n 番目に大きいキーの位置の下限を考えようとしています。ヒープが配列に配置されていると仮定します。上限の min(2^n-2, array size -1) だと思いますが、下限は常に 0 ですか?

バイナリ ヒープから最小値を抽出しようとしていますが、うまくいきません。ここに私のBubbleDownコードがあります:

いくつかの数字だけを交換しているように見えますが、すべてではありません。理由がわかりません。私はそれを別の方法で再コーディングしようとしましたが、すでに何度も...

私は何を間違っていますか？

バイナリヒープの最小要素を削除した後、つまりルートを削除した後、ヒーププロパティを維持するにはヒープを調整する必要があることを理解しています。しかし、これを行うための好ましい方法は、最後の葉を根に割り当ててふるいにかけることです。

なぜ私たちは根であったもののより小さな子を取り出さず、すべての子をふるいにかけ続けるのか疑問に思っています. これは同じ量の操作ではないのに、なぜ「最後の葉をルートに割り当ててふるい落とす」方法が好まれるのでしょうか?

フィボナッチヒープとバイナリヒープの実際のアプリケーションは何ですか？問題を解決するためにそれを使用したときに、いくつかのインスタンスを共有できれば素晴らしいと思います。

編集：バイナリヒープも追加しました。知りたい。

私はデータ構造コースを受講しており、Mark Weiss による Java 2nd Edition のデータ構造とアルゴリズム分析を使用しています。彼の BinaryHeap 実装では、彼のコンストラクターは、AnyType[] にキャストされる Comparable[] 配列を作成します。彼が単に新しい AnyType[] を作成するのではなく、なぜこれを行うのかについて何か考えはありますか?

BinaryHeap の構造は理解していますが、ジェネリックについては理解を深めたいと思っています。クラス宣言は単純明快です。AnyType が、AnyType に相当する型または AnyType の継承階層を上るスーパークラスを拡張することを確認してください (AnyType が型のサブクラスであり、機能するためにその compareTo メソッドを変更する必要がない場合)。 ）。

しかし、行 ,array = (AnyType[]) new Comparable[ capacity + 1 ];は私には意味がありません。AnyType はすでに Comparable ではありませんか? 書くだけでどんな影響がありarray = new AnyType[ capacity + 1 ];ますか？

完全なクラスのソースは彼のサイトにありますが、私が懸念している部分は次のとおりです。