0
$\begingroup$

I have these 4 symbols with their probabilities:

 x   P(x)
 --------
 1   0.3
 2   0.3
 3   0.2
 4   0.2

I built the Huffman tree in this way:

enter image description here

and I obtainded:

 x   P(x)   C(x)
 ----------------
 1   0.3     0
 2   0.3     10
 3   0.2     110
 4   0.2     111

it's correct? Because according to the solution the results should be:

 x   P(x)   C(x)
 ----------------
 1   0.3     00
 2   0.3     01
 3   0.2     10
 4   0.2     11

Why? Yet I followed the steps shown here.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented May 27, 2016 at 19:23
  • $\begingroup$ Please don't delete your question after you get an answer. That's disrespectful to the person who spent time writing an answer. We want to build up an archive of high-quality questions and answers that will help not only you but others as well; deleting the question prevents anyone else from benefiting, and prevents the person who answered from receiving reputation for their answer. Thank you! $\endgroup$
    – D.W. ♦
    Commented Jun 2, 2016 at 6:36

1 Answer 1

Reset to default
2
$\begingroup$

A quick way to check whether your answer has a chance of being correct is to compute the average code length. Your encoding gives the average length of $2.1$, which is greater than using a code of fixed length $2$, so it can't be correct.

If you follow the priority queue algorithm from the source you cite, then you would notice that after merging nodes 3 and 4 you get one supernode of priority 0.4. Now your queue would have three elements of priorities $0.3, 0.3,$ and $0.4$. Thus, you would next merge elements corresponding to priorities $0.3$ and $0.3$ (the algorithm works by merging two nodes with lowest priorities), which happen to be nodes 1 and 2.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.