問題タブ [binary-heap]

ノードをバイナリ ヒープに挿入したい場合、挿入とヒープ化後にヒープ内のノードのインデックスを見つけるにはどうすればよいですか? バイナリ ヒープは配列として表されます。このアルゴリズムを O(log(log(n))) で見つける必要があります。

log n の複雑さでそれを見つける方法は知っていますが、log log n で見つけることができません。

皆さん、ありがとうございました。

プロジェクトのコードを閲覧しているときにBinaryHeap、2 つの実装 (Array と Tree を使用) がインターフェイス自体の内部にパックされている実装を見つけました。やや複雑に感じました。コードは次のとおりです。

このアプローチに問題はありますか？読みやすさの点でどのように改善できますか？

私は配列を持っていて、この式で2$heap = array(9, 9, 9, 8, 9, 9, 8, 9, 9, 9, 9, 9, 8, 8, 9, 7, 9, 8, 8, 9, 9,);つの子ノードを知ることができるとき、バイナリツリーのように出力したいと思います。foreach を使用して実行しようとしましたが、未定義のオフセット 21 に関するエラーが発生しました。これが foreach です。$heap[$key*2+1]$heap[$key*2+2]

私が間違っていることと、これを解決するにはどうすればよいですか?

私が見たBSTのほとんどの例は、次の形式です

ただし、BST は、追加の制約を伴う特定の形式のバイナリ ヒープのように見えます。つまり、左の子の値は、右のノードの値より小さくなければならない親の値より小さくなければなりません。

バイナリ ヒープは、配列を使用して簡単に実装できます。この特別な規則が確実に維持されるように、配列を使用して BST を作成してみませんか? そうすることの欠点は何ですか？

最小削除操作ではバイナリ ヒープが高速であり、優先度を下げる操作では d-ary ヒープが高速であることを読みました (理由はわかりませんが)。どちらもバイナリヒープと比較されます。

では、いつバイナリ ヒープを使用し、いつ D-ary ヒープを使用するのでしょうか? また、d-ary ヒープの d を決定するにはどうすればよいですか?

DSA のクラスを受講してから 10 年近くになります。ウィキペディアの並べ替えアルゴリズムのリストを調べましたが、これほど目立ったものはありません。これはプライオリティ キューの実装の一部であり、並べ替えの一部はプッシュ関数 ( EnQueue) で発生し、もう 1 つはポップ関数 ( DeQueue) で発生するようです。

これが元のMathematicaコードですが、ほとんどの人はMathematicaに慣れていないので、各関数の下を少し翻訳しました。

このEnQueue関数は、最初に要素数がnheap のサイズに達しているかどうかを確認し、達しているar場合はヒープを 2 倍にします。次に、要素の数を増やし、新しい要素をそのインデックスに格納します( Mathematicaのインデックスは0ベースではなく1ベースです)。次に、(新しい要素の) そのインデックスに設定し、にi設定するループに入ります。つまり、ヒープの中央にある要素です。ここで、 if (これは、私が知る限り、 if (中間の要素)が(新しい要素) の前にあることを確認することと同じです)、ブレークします。それ以外の場合は、とで要素を交換しますjfloor(i/2)j < 1i == 1ar[j]ar[i]ij、そして続けます。そのため、2 回目の反復では、中央をi指すことから始め、 4 分の 1 を指すようにします。j

一方、ヒープの前面を戻し、ヒープの背面DeQueueを前面に移動します (そして、背面の設定を解除し、要素の数を減らします)。次に、前を指すことから始まり、double に設定することから始まるループに入ります。範囲内(要素を指している) であるが、次の要素に関して順不同である場合、インクリメントされます。が (フロントに対して、つまり、フロントがに対して順不同である場合)の場合、2 つの位置が交換され、 があった位置に設定されます。真ん中を通過するまでループを続けます。jijiiijijij

上記の太字の部分がほとんどで、わかりません。でヒープの半分をソートし、 で新しい要素のソートの一部を行っていると思いますが、よくわかりません...DeQueueEnQueue

私は現在、次のことを要求される宿題に取り組んでいます。

バイナリ ヒープを使用した単一ソース最短経路問題に対する DIJKSTRA のアルゴリズムを実装します。実行時間は O(ElogV) である必要があります。

簡単です！ただし、問題はコードで解決する必要があります。これまでは、それほど難しい概念ではありません。

プログラムはファイルからデータを読み取り (以下のサンプルを参照)、ノード 0 から各ノードまでの最短パスの長さの合計を 1 つの数値として出力する必要があります。入力フォーマット: 以下の各ファイルの最初の行には、グラフ内の頂点の数とエッジの数が含まれています (「n=XXXX m=XXXXX」の形式)。ファイルの残りの部分は、次のように編成されています。各頂点 i が 1 行に表示され、その後に i の隣接 j>i (j とエッジの長さ (i,j) を含む) の行が続きます。ネイバーの各リストは、空の行で終了します。i より大きいインデックスを持つ隣接頂点を持たない頂点 i は表示されません。注: 頂点には 0 から n-1 までのインデックスが付けられます。注: 各エッジは、小さい方のエンドポイントで 1 回だけ言及されます。 サンプル入力: 1.最初の入力 2.2 番目の入力 の最短パス ツリーの長さは、それぞれ 10721073 と 625349 である必要があります。プログラムは、最初の入力では 3 ～ 10 秒、2 番目の入力では 1 秒未満で出力を返す必要があります。

私の質問:ファイルの形式とコードでの変換方法に関する教授の説明がよくわかりません。視覚化する必要があるグラフの種類もわかりません。二分木で最短経路を見つけているのでしょうか、それとも多くの頂点と辺を持つグラフ (二分木ではない) で最短経路を見つけているのでしょうか? (彼が Binary Heaps について言及しているため、私は混乱しているため、ここで何を視覚化すればよいかわかりません)

よくわからないファイルについて:グラフを見ると、次のようになっています。

n = number of vertices彼の説明から、それとm = number of edges. 私が理解していないのは、頂点の後の数値のペアが、0ダイクストラのオンを使用することになっているグラフに関して何を表しているかです。また、いずれかのファイルの末尾を見ると、この形式でリストされている頂点の数が、n ='s. どうしてこれなの？

以下は、配列ベースのプライオリティ キュー/バイナリ ヒープの再帰的 heapify 関数です。

無限再帰に入る理由を誰か教えてもらえますか?

わかりましたので、無限ループを修正しましたが、関数はまだ正しくヒープ化されません。

これが新しいコードです。