2

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:

9
1
2
3
3
2
1
1
2
3

Then my min-heap would look like so:

               1
          /         \
        2            1 
     /     \        /  \
    2       2      3    1
   /  \
  3    3

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.

4

2 に答える 2

2

これは、従来のアルゴリズムを少し変更するだけで実現できると思います。優先キュー ヒープに単一のツリーを格納する代わりに、隣接するツリーのペアを格納します。(t1, t2)次に、各ステップで、最小のペアと、それらの木を含む最大 2 つのペア、つまり(u, t1)とを削除します(t2, r)。次にマージt1しt2て新しいツリーに、ペアをt'再挿入し、更新された重みでヒープに挿入して繰り返します。(u, t')(t', r)

于 2012-10-27T06:35:15.377 に答える
0

2 つのツリーをポップして、3 つ目のツリーを作成する必要があります。左側のノードでは合計が小さいツリーに結合し、右側のノードでは 2 番目のツリーに結合します。このツリーをヒープに入れます。あなたの例から

ヒープから 2 つのツリーをポップします。

1 1

木を作る

  ?
 / \
?   ?

小さいツリーを左のノードに配置

min(1, 1) = 1

  ?
 / \
1   ?

ノードの 2 番目のツリーを右に配置

  ?
 / \
1   1

あなたが作ったツリーは合計=左ノードの合計+右ノードの合計を持っています

  2
 / \
1   1

新しいツリー (合計 2) をヒープに入れます。

最後に、ハフマン木です。

于 2012-10-27T06:23:58.593 に答える