The greedy-choice property for Huffman's algorithm.


R. Clayton (rclayton@monmouth.edu)
Wed, 19 Apr 2000 17:25:29 -0400 (EDT)


In class we got W(To) >= W(T') and then drew the conclusion that W(T') is also
an optimal tree. However, I question that conclusion.

  Yes, I botched that one, didn't I? Here's the logic behind the proof:

    By assumption, the tree To is optimal, which means, for any other tree T',

      w(To) <= w(T')

    Now, if I can also show that w(To) >= w(T') holds, then I have

      w(To) <= w(T') and w(To) >= w(T') -> w(To) = w(T')

    that is, T' is also an optimal tree.

If To is an optimal tree, then it has minimum weight. However, by exchanging
two items x and b we arrive at a tree that has a lower weight

  Stop right there: we arrive at a tree T' that has weight no greater than To,
  which is not the same thing as a lower weight (or a weight less than).

  It's the equal part of "greater than or equal to" that saves us.



This archive was generated by hypermail 2.0b3 on Wed Apr 26 2000 - 09:35:05 EDT