0
$\begingroup$

I saw the following claim:

Given $Q=\{1,2,\dots,n\}$ and $f$ (positive function) such that:

$$f(1)>f(2)>\dots>f(n)>f(1)/3$$

Then there are leafs at maximum 3 different levels of Huffman tree.

I have been looking for a counterexample but no luck, can someone help me?

New contributor
coolmo is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
7
  • $\begingroup$ How large can $n$ be? $\endgroup$ – Yuval Filmus Jun 6 at 15:25
  • $\begingroup$ @YuvalFilmus any normal number, why? $\endgroup$ – coolmo Jun 6 at 16:20
  • $\begingroup$ Please credit the source of all copied material. $\endgroup$ – D.W. Jun 6 at 20:21
  • $\begingroup$ What is the relationship between the Huffman tree and $f$? $\endgroup$ – D.W. Jun 6 at 20:21
  • $\begingroup$ If $n=1$, what happens? If $n=2$, what happens? $\endgroup$ – D.W. Jun 6 at 20:23

Your Answer

coolmo is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.