問題タブ [binary-heap]

n 個の数値を含むバイナリ ヒープを考えてみましょう (ルートには最大の数値が格納されます)。正の整数 k < n と数値 x が与えられます。ヒープの k 番目に大きい要素が x より大きいかどうかを判断する必要があります。アルゴリズムは O(k) 時間かかる必要があります。O(k) 追加ストレージを使用できます

バイナリ ヒープは 2 つの子 (ツリー表現) しか持つことができず、二項ヒープは任意の数の子を持つことができるという構造の違いに関係なく、バイナリ ヒープと二項ヒープの主な違いを知る必要があります。

実際、最初の子が 1 つのノードに 2 番目に 2 番目に 2 番目に 4 番目にあるというように二項ツリー構造を編成する際に何が特別なのか疑問に思っています。

2 つの子を制限せずにヒープに通常のツリーを使用し、結合手順を適用して、1 つのヒープを他のヒープの左側の子にする場合はどうなるでしょうか。

C++0x 標準を調べたところ、make_heap は 3*N 回を超えない比較を行う必要があることがわかりました。

つまり、順序付けられていないコレクションを O(N) でヒープ化できます。

どうしてこれなの？

ソースから手がかりが得られない (g++ 4.4.3)

while (true) + __parent == 0 は手がかりではなく、O(N) 動作の推測です

__adjust_heap は、log N メソッドのように見えます。

私にとってはボグスタンダードのログNです。

これが O <= 3N である理由の手がかりをいただければ幸いです。
編集：

実験結果：

この実際の実装では

• ヒープ化ヒープの <2N 比較
• ヒープを逆の順序でヒープ化する場合は <1.5N。

優先キューを表すバイナリヒープを作成しました。これは、古典的なよく知られたアルゴリズムです。このヒープは、さまざまなイベントの時系列シーケンスをスケジュールします（ソートキーは時間です）。

挿入と削除の2つの操作をサポートします。ヒープの各ノードのキーは、その子のそれぞれ以上です。ただし、同じキーでイベントを追加しても、追加された順序は保持されません。これは、削除または挿入が呼び出された後、ヒープアップおよびヒープダウンプロシージャが順序を壊すためです。

私の質問は、同じ優先順位を持つノードの順序を維持するために、従来のアルゴリズムで何を変更する必要があるかということです。

バイナリ ヒープについて調査しましたが、このプログラムをどうするかについてまだ非常に混乱しています。何らかのガイダンスを得ることができれば、本当に感謝しています。

k-ary ヒープはバイナリ ヒープ (k = 2) に似ていますが、(1 つの例外を除いて) 非リーフ ノードには 2 つの子ではなく k 個の子があります。次の操作をサポートするために、任意の k ≥ 2 の最小優先度キューとして k-ary ヒープを実装します。

• insert (x): 要素 x をヒープに挿入します。

• extract-min(): 最小のキーを持つヒープの要素を削除して返します。

k-ary ヒープは、事前定義されたサイズの配列を使用して実装されます。また、k = 2、4、6、8、10 の入力ファイルが与えられた場合に一連の操作を実行するのに必要な時間を測定することにより、さまざまな k の値に対するデータ構造の相対的な効率を調べます。入力ファイルでは、「IN」は略「EX」はインサートの略で、「EX」は抽出分操作の略です。

バイナリヒープを学習しようとしていますが、バイナリヒープで削除操作を実行することに疑問があります。バイナリヒープから要素を削除できるので、それを再ヒープ化する必要があることを読みました。

しかし、次のリンクでは、利用不可と表示されています。

http://en.wikibooks.org/wiki/Data_Structures/Tradeoffs

私はそれについて少し混乱しています。

すべての説明を事前に感謝します。

さて、テキストファイル（必ずしもすべての可能な記号が含まれているとは限りません）があり、各記号の頻度を計算したいとします。頻度を計算した後、各記号とその頻度に最も頻繁にアクセスする必要があります。最も頻度が低い。シンボルは必ずしもASCII文字である必要はなく、すべて同じ長さであっても、任意のバイトシーケンスである可能性があります。

私はこのようなことを（擬似コードで）行うことを検討していました：

私は疑問に思っていました：各シンボルがファイルに出現する回数を計算して保存するためのより良い、より簡単な方法はありますか？

n個の要素のバイナリヒープがあり、さらにn個の要素を挿入したいとします（必ずしも次々に挿入する必要はありません）。これに必要な合計時間はどれくらいですか？

1回の挿入でlognが必要になるため、シータ（n logn）だと思います。

タイトルで言及されているものの中で、1つまたは別のヒープ実装を使用するかどうかをどのように決定すればよいか、誰かが私に説明してもらえますか?

問題に応じて、構造のパフォーマンスに関する実装を選択する際のガイドとなる回答が欲しいです。現在、優先キューを実行していますが、この場合に最も適切な実装だけでなく、他の状況で実装を選択できるようにする基本を知りたいです...

他に気になる点としては、今回は haskell を使っているので、この言語での実装を改善する裏技や何か知っていることがあれば教えてください! 以前と同様に、他の言語の使用に関するコメントも大歓迎です!

ありがとう！質問が基本的すぎる場合は申し訳ありませんが、私はヒープにまったく慣れていません。実装のタスクに直面するのはこれが初めてです...

再度、感謝します！

これは宿題の質問で、8 要素のバイナリ ヒープには 8 つの比較が必要であることを示すよう求められています。

しかし、次のような例を使用すると、 1 2 3 4 5 6 7 8 ボトムアップとトップダウンのどちらにすべきかわかりません。とにかく、私は両方を試しました。

トップダウン: 8 つのステップで実行しましたが、比較の数を数えると 13 になります:S

ボトムアップ：私は7つのステップでそれをやったが、比較の数を数えると10になる：S

ここでアルゴリズムを試した後、私が得た比較は次のとおりです。

1. H[L]=8 > H[i]=4
2. H[L]=8 > H[i]=2、H[r]=5 > H[最大]=8
3. H[L]=4 > H[i]=2
4. H[L]=6 > H[i]=3、H[r]=7 > H[最大]=6
5. H[L]=8 > H[i]=1、H[r]=7 < H[最大]=8
6. H[L]=4 > H[i]=1、H[r]=5 > H[最大]=4

うーん、比較の数を数えて8つ表示できるようにするにはどうすればよいですか？どの方法を使用しますか (ボトムアップまたはトップダウン)?