問題タブ [min-heap]

私は問題を解決するために最小ヒープを学習して実装しようとしています：doubleを作成し、それらをソートされた配列に挿入するループ、C

基本的に、私は最小から最大にソートされたダブルのセットから始めます。次に、doubleを（おそらくランダムに）生成し、新しく生成されたdoubleを、ソートしたままセットに追加する必要があります。また、ダブルを挿入するたびに、セットから最小のダブルを削除します。

（編集-セットを完全にソートする必要はありません。目標は、doubleを挿入するたびに最小要素を検索して削除できるようにすることです。セットをソートしたままにすることが、私の最初の素朴な解決策でした。）

最小ヒープが実行されたようなもののように聞こえます。

試み

Cでは、配列サイズが事前に宣言されているため、長さ=最終的に得られるdoubleの最大数の配列を作成する必要があります。次に、この配列のすべてのエントリに値max_doubleを入力します。

ここでガイドとして説明されているメソッドを使用して：http：//opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html、この配列に値を挿入および削除する関数を作成できます。

挿入：配列の最後のエントリ（常にmax_doubleになります）を数値に置き換えます。次に、親ノードの値が新しく追加された値より小さくなるまで、親ノードの値と交換し続けます。

削除：ルートノードをmax_doubleに置き換えてから、その2つの子と比較し、2つの子がmax_doubleになるまで最小の子と交換します。

質問

私はこれらすべてに正しいアプローチを使用していますか？

重複の可能性:
Python での最大ヒープの実装には何を使用しますか?

Python の heapq を何らかの方法で実装しようとしていますが、max-heap 用です。解決策は、(-1) と複数のキューを使用することですが、ヒープに URL を保存する必要があるため、これは役に立ちません。したがって、最大値をポップできる最大ヒープが必要です。

I am working on an assignment for an Algorithms and Data Structures class. I am having trouble understanding the instructions given. I will do my best to explain the problem.

The input I am given is a positive integer n followed by n positive integers which represent the frequency (or weight) for symbols in an ordered character set. The first goal is to construct a tree that gives an approximate order-preserving Huffman code for each character of the ordered character set. We are to accomplish this by "greedily merging the two adjacent trees whose weights have the smallest sum."

In the assignment we are shown that a conventional Huffman code tree is constructed by first inserting the weights into a priority queue. Then by using a delmin() function to "pop" off the root from the priority queue I can obtain the two nodes with the lowest frequencies and merge them into one node with its left and right being these two lowest frequency nodes and its priority being the sum of the priorities of its children. This merged node then is inserted back into the min-heap. The process is repeated until all input nodes have been merged. I have implemented this using an array of size 2*n*-1 with the input nodes being from 0...n-1 and then from n...2*n*-1 being the merged nodes.

I do not understand how I can greedily merge the two adjacent trees whose weights have the smallest sum. My input has basically been organized into a min-heap and from there I must find the two adjacent nodes that have the smallest sum and merge them. By adjacent I assume my professor means that they are next to each other in the input.

Example Input:

Then my min-heap would look like so:

The two adjacent trees (or nodes) with the smallest sum, then, are the two consecutive 1's that appear near the end of the input. What logic can I apply to start with these nodes? I seem to be missing something but I can't quite grasp it. Please, let me know if you need any more information. I can elaborate myself or provide the entire assignment page if something is unclear.

ハフマン ツリーから正しくポップするのに問題があります。現在、minheap に基づいてハフマン ツリーを作成しており、次のことを行いたいと考えています。

A と B が 2 つの異なるサブツリーであると仮定すると、A の頻度が B の頻度よりも低い場合、A が最初にポップオフされると言えます。それらが同じ頻度である場合、A の葉ノードのいずれかで ASCII 値の最小文字を見つけます。次に、A の最小の文字リーフ ノードが B のリーフ ノードよりも小さいかどうかを確認します。もしそうなら、私はBの前にAをポップオフします。そうでなければ、Bをポップオフします. <-これは私が問題を抱えていることです.

例えば：

私が入力したとしましょう：

私のハフマンツリーに。次に、私のツリーは次のようになります。

以下は、Huffman minheap から飛び出すための私の試みです。2つの文字の頻度が同じかどうかを比較する部分に問題があります. 誰かが助けてくれれば、それは素晴らしいことです。ありがとう！

stl プライオリティ キューから最小ヒープを作成しています。これが私が使用している私のクラスです。

};

主に、このようにオブジェクトをインスタンス化します。

理解できないエラーが発生しxutilityています。

d:\microsoft visual studio 10.0\vc\include\xutility(674): エラー C2064: 用語が 2 つの引数を取る関数に評価されません

その解決策への助けをいただければ幸いです。

STL などを使用して C++でs の最小ヒープ¹を作成しようとしていますが、コンパレータが正しく比較されていないようです。以下は私の現在のコンパレータです：longmake_heap

ただし、std::pop_heap(humble.begin(),humble.end(),g);where gis an instance greater1and humbleis a heap who make [9,15,15,25]whensort_heapが呼び出されると、15ポップが発生します。

私のコンパレータは正しいですか？何がうまくいかないのですか？

編集:
コンパレータなしで sort_heap を実行していることに気付きましたが、このコンパレータを実行すると[15,15,9,25]、sort_heap. 今、私はコンパレーターが確実に機能していないと考えていますが、その理由は不明です。

¹ STL はデフォルトで max-heap を作成するため、コンパレータが必要です。

最小ヒープを使用して k 番目に大きい要素を見つけることについて質問があります。アルゴリズムは次のとおりです。

1. 最初の k 要素を取り、最小ヒープを構築します

2. S の最小の要素を Sk とします。

3. 残りの nk 個の要素から、新しい要素を見てください。

4. 新しい要素が Sk よりも大きい場合は、S でそれを置き換え、ヒープを並べ替えます。

5. S は新しい最小要素を持つことになります。

6. 他のすべての要素を見た後、Skが答えです

このアルゴリズムがわかりません。たとえば、数値を 1、2、3、4 とします。4 番目に大きい 4 を見つけたいとします。しかし、アルゴリズムを使用する場合、最初の 4 つの要素を取得して最小ヒープを構築すると、Sk は 1 になります。

私は何を間違っていますか？誰かが助けてくれれば幸いです。ありがとう

そこで、二分木の最小ヒープを作成しました。それをテストするために、2 つの異なる値を持つ一連のノードを作成します。

言う

ヒープが主にソートするのは頻度であるとしますが、ノードの頻度が同じ場合は、ノードのデータでソートします。

ノードの束を作成し、ヒープをロードし、それらをポップして印刷すると、取得します(サイズはツリー内のノードの数であり、最小は各ツリーが保持する最小データです)

気付かなかった場合は、3 番目のエントリが間違っているため、ヒープが間違っています。

私のバグは、minheap upheap downheap、remove、または insert のどこかにあります。

シムシティのような他の多くの楽しいことをするために、私は何日も試みてきましたが、私の脳はそれを処理できません。（そうでもない、私はこれを終わらせなければならない）

これが私のヒープです

独自の STL クラスを作成する必要があることに言及する必要があります。頻度が同じ場合、ヒープはツリーに保持されている最小値で優先順位を選択することも想定されているため、コード内のミンキー ポインターはそのようになっています。正しい順序ではない理由を理解する必要があります。

私のプログラムはハフマン コーダー用です 。

ubuntu 64 システムでコンパイルする make ファイルがあります。入力にリダイレクトを使用します。

上記のヒープは
echo "Sally Sold Sea Shells By The Sea Shore" > input
./huff < input から取得されます

最小ヒープを構築しようとしています。挿入、削除、スワップ、アップヒープ、ダウンヒープはすでに実行されており、正しく機能しています。

ただし、Min-Heapifyのメソッドを作成しようとしています。

これが私の入力です：{20,14,9,6,4,5,1}

私が期待した出力は、最小ヒープの場合です：{1,5,4,20,9,6,14}しかし、私が得たのは：{1,6,9,20,4,5,1}です。反対。

これが私のコードです：

MAX-Heapifyのこの擬似コードに従いました

minHeapクラスをmaxHeapクラスに変換しようとしています。minHeapクラスのコードが与えられました。その1つのメソッドはaddでした。次のようになります。

最初のノードは自動的にnullに設定されるため、追加されるものはすべてノード1以降に配置されます。すでに述べたように、このコードはminHeap構造を与えます。したがって、maxHeapに変更します。コンパレータの符号を次のように反転します。

入力している項目は整数値で格納されています。挿入順に次のとおりです。

minHeap構造では、これらは次のようにノードに格納されます。

maxHeap構造では、符号を変更すると次のように格納されます。

minHeap構造体の場合と同じ種類の順次順序ではなくなったことに注意してください。これは重要ですか、それともまだ有効なmaxHeapですか？

木のような構造を見せようとした私のひどい試みについてお詫びします。