algorithm design techniques sp nl figure huffman' algorithm after the fifth merge nextwe must show that the two least frequent characters and must be the two deepest nodes (although other nodes may be as deepagainthis is easy to show by contradictionsince if either or is not deepest nodethen there must be some that is (recall that the tree is fullif is less frequent than then we can improve the cost by swapping them in the tree we can then argue that the characters in any two nodes at the same depth can be swapped without affecting optimality this shows that an optimal tree can always be found that contains the two least frequent symbols as siblingsthusthe first step is not mistake the proof can be completed by using an induction argument as trees are mergedwe consider the new character set to be the characters in the roots thusin our exampleafter four mergeswe can view the character set as consisting of and the metacharacters and this is probably the trickiest part of the proofyou are urged to fill in all of the details the reason that this is greedy algorithm is that at each stage we perform merge without regard to global considerations we merely select the two smallest trees if we maintain the trees in priority queueordered by weightthen the running time is ( log )since there will be one buildheap deleteminsand insertst nl figure huffman' algorithm after the final merge sp