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
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