問題タブ [binomial-heap]

私の目的は、二項ヒープを構築することです。ここに私が今書いたコードがあります：

簡単な解決策は、2 つの配列を 3 つ目の配列に結合してから buildmax プロシージャを呼び出すことだと思いますが、効率的ではないと思います。ウィキペディアからこの疑似コードを実装しようとしました

しかし、一般的にサブツリーにアクセスする方法があるため、それを実装する方法がわかりません?別のバリアントは、優先キューを構築し、挿入関数を使用して、最初に1つの配列から挿入し、次に別の配列から挿入しますが、これは最適ですか?コードを書くのを手伝ってくださいこれら 2 つの最大ヒープを 1 つに効率的に結合するには

私のコードは仕事をしていると思いますが、「nsteps」を 5 より大きくするとクラッシュします...さまざまなエラーが発生し続けます...5 より大きいとコードに問題があるとだけ表示されます... 「??? 最大再帰制限の 500 に達しました。set(0,'RecursionLimit',N) を使用して制限を変更してください。使用可能なスタック領域を超えると、MATLAB やコンピューターがクラッシュする可能性があることに注意してください。」

誰でも問題を見つけることができますか？まず、AmericanPutClassic(100,0) を呼び出します...

ありがとう

誰かが素集合データ構造とは何かを説明できますか？あるいは、それをうまく説明しているYouTubeビデオまたは記事に私をリンクできますか？

数分前に検索したところ、ベン図のような画像を使った数学のレッスンしか受けられませんでした。たぶんそれだけですが、よくわかりませんので、よろしくお願いします。

簡単に言うと、「バイナリツリーを使用して二項キュー内の各二項ツリーを表す方法」と尋ねられたとき、これは互いに積み重ねる必要のある二項ツリーを指します。B1がB1に接続してB2になるように、2つのB2がB3になり、以下同様に続きます。

「Introduction to Algorithm」という書籍で提供されている二項ヒープの減少キーのインターフェイスは次のとおりです。キーが k に減らされるノードの「インデックス」。時間計算量は O(logn)

ただし、通常、リンクされたリストを使用して二項ヒープを実装します。この場合、検索を実行せずに x に直接アクセスすることはできません。これは一般に O(n) です。

この問題を解決する 1 つの方法は、二項ヒープ内の各ノードのポインターを保持することです。これにより、O(1) 内のすべてのノードに直接アクセスできますが、空間の複雑さは O(n) になります。

これに対するより良い解決策を知っている人はいますか？ありがとう！

以前の議論はここにあります。

このステートメントの適切な証拠を見つけるのに苦労しています。nのバイナリ表現を使用して決定される二項ツリーの数を決定する方法を知っています。たとえば、13 要素はバイナリで 1101、2^{3}+2^{2}+2^{0} したがって、3 つの二項ツリーが必要であり、ln(13) + 1 = 3.56 > 3

log(n) で制限されていることを証明する方法がわかりません。一般に、log(n) を含むアルゴリズムの多くの概念に苦労しています

誰かがこの声明の明確で簡潔な証拠を提供できますか?

O(n log n) 未満の最悪の場合の複雑さ、つまり n 個の連続した挿入を使用して、指定された n 個の要素を持つ二項ヒープを最初に構築する方法はありますか? (挿入の償却コストが O(1) であることはわかっているため、ビルドの平均時間の複雑さは小さくなります。) バイナリ ヒープの場合、n 個の要素すべてをバイナリ ツリーに入れ、heapify/siftDown を実行する、より効率的なビルド実装があります。要素の前半を逆順で。疑問に思っているのは、二項ヒープに対して同様に賢いものが存在するかどうかです。

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

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

高速な挿入が可能で、挿入のたびに重複することなくデータをソートできるデータ構造を実装したいと思います。

二項ヒープについて考えましたが、その構造について理解したのは、特定の要素がまだヒープにあることを挿入中に判断できないということです。一方、私のケースに完全に適合するAVLツリーがありますが、正直なところ、現時点では実装するには難しすぎます。

私の質問は次のとおりです。二項ヒープ挿入アルゴリズムを編集して重複をスキップする可能性はありますか? たぶん、誰かが別の構造を提案できますか？

グレッティング:)