Given the following set of character-probability ps: ( B is the part where I nee

Question

Given the following set of character-probability ps: ( B is the part where I need help with)

(I asked this question but wasn't given the answer I was looking for.To be more specific I need help with a final number.)

Exmp of final answer ( Unit of times used=86);

(A,0.2), (B,0.1), (C,0.3), (D,0.15), (E,0.05), (F,0.2)

)Build a Huffman tree for this character set

B) Assume that enqueue, dequeue, peek, creating a leaf node, creating a new tree out of two subtrees, and picking the minimum of two probabilities all take unit time. Ignore the time for all other operations. How many units of time did it take in all to build your tree? Show your work.

*This is what the guy who answered the first part said the Huffman tree looked like(this part I understand, I just need help analyzing the peek,deeque,creating leaf,new tree subtress and getting a final number)

Explanation / Answer

Huffman(C)

{

n=|C|

Q = C

for i=1 to n-1

create a new node p

p.left = x = Extract-Min(Q)

p.right = y = Extract-Min(Q)

p.prob= x.prob + y.prob

Insert(Q, p)

return Extract-min(Q) // return the root of the tree

}

Here C is a set of characters and each character c belonging to C is an object with an attribute c.prob giving its probability. The algorithm builds the tree T corresponding to the optimal code in a bottom-up manner. It begins with a set of |C| leaves and performs a sequence of |C| - 1 merging operations to create the final tree. The algorithm uses a min-priority queue Q, keyed on the prob attribute, to identify the objects with least probability to merge together. When we merge two objects, the result is a new object whose probability is the sum of the probabilities of the two objects that were merged.

ANALYSIS:

Foe a set C of n characters, we can initialize Q in O(n) time.

The for loop executes exactly n-1 times and since each heap operation requires time O(log n), the loop contributes O(n log n) to the running time.Thus the total running time of Huffman on a set of n characters is O(n log n).

We can not tell the exact running time because it is always machine-dependent.

Roughly the unit of time taken would be n*log n = 6*log6 = 6*0.78 = 4.68 units

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.