minimum weighted path length

Given a list of weights, $W:=\left\{w_{1},w_{2},\dots,w_{n}\right\}$, the minimum weighted path length is the minimum of the weighted path length of all extended binary trees that have $n$ external nodes with weights taken from $W$. There may be multiple possible trees that give this minimum path length, and quite often finding this tree is more important than determining the path length.

Example

Let $W:=\left\{1,2,3,3,4\right\}$. The minimum weighted path length is $29$. A tree that gives this weighted path length is shown below.

Applications

Constructing a tree of minimum weighted path length for a given set of weights has several applications, particularly dealing with optimization problems. A simple and elegant algorithm for constructing such a tree is Huffman’s algorithm. Such a tree can give the most optimal algorithm for merging $n$ sorted sequences (optimal merge). It can also provide a means of compressing data (Huffman coding), as well as lead to optimal searches.

Title minimum weighted path length MinimumWeightedPathLength 2013-03-22 12:32:12 2013-03-22 12:32:12 mathwizard (128) mathwizard (128) 6 mathwizard (128) Definition msc 05C05 WeightedPathLength ExtendedBinaryTree HuffmansAlgorithm HuffmanCoding