# minimum weighted path length

Given a list of weights, $W:=\{{w}_{1},{w}_{2},\mathrm{\dots},{w}_{n}\}$, 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:=\{1,2,3,3,4\}$. 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 |
---|---|

Canonical name | MinimumWeightedPathLength |

Date of creation | 2013-03-22 12:32:12 |

Last modified on | 2013-03-22 12:32:12 |

Owner | mathwizard (128) |

Last modified by | mathwizard (128) |

Numerical id | 6 |

Author | mathwizard (128) |

Entry type | Definition |

Classification | msc 05C05 |

Related topic | WeightedPathLength |

Related topic | ExtendedBinaryTree |

Related topic | HuffmansAlgorithm |

Related topic | HuffmanCoding |