{c}

For a finite source <alphabet> of $n\geq2$ symbols with positive weights $w_x$, choose any two least weights, breaking ties arbitrarily. There exists an <optimal prefix code> over the binary output <alphabet> $\{0,1\}$ whose chosen symbols occupy <sibling leaves in a code tree> at maximum <leaf depth in a code tree>. Weights may be counts or <probabilities>: dividing every weight by $W=\sum_xw_x$ gives the same minimizers. The existence statement is what makes the first merge of <Huffman coding> safe. It does not say that every <optimal prefix code> already has the chosen pair together.<A Method for the Construction of Minimum-Redundancy Codes by David A. Huffman>[p. 1099: Derived Coding Requirements and Optimum Binary Code]{ref}

An exchange makes the idea tangible. Take <probabilities> $(p_A,p_B,p_C,p_D)=(0.4,0.3,0.2,0.1)$. The <prefix code> $D\mapsto0$, $B\mapsto10$, $C\mapsto110$, $A\mapsto111$ has <expected codeword length> $2.5$ <bits>. Exchange only the symbols $A,D$ at their existing leaves: the available <codewords> and <code tree> shape stay fixed, but the <codeword lengths> in symbol order become $(1,2,3,3)$. The new <expected codeword length> is $1.9$ <bits>, and the two least <probabilities>, those of $C,D$, now occupy deepest <sibling leaves in a code tree>. The saving is $(0.4-0.1)(3-1)=0.6$ <bit> per source symbol.

\Image[/prefix-tree-leaf-exchange-and-contraction.png]
{title=Exchanging two leaf labels reduces expected length from 2.5 to 1.9 bits; contracting the least-probability siblings leaves cost 1.6}
{id=prefix-tree-leaf-exchange-and-contraction}

Here is the short proof outline. An <optimal prefix code> with positive weights has a <full binary tree> as its <code tree>: suppressing a <vertex> with only one child shortens every <codeword> in that <subtree> and strictly reduces cost. A deepest leaf therefore has a leaf as its sibling, giving the <deepest sibling property of an optimal prefix code>. Put the two chosen least weights at these positions by successive exchanges of leaf labels. Moving a weight $a$ from <leaf depth in a code tree> $d$ to a deepest position $D\geq d$, occupied by $b\geq a$, changes the weighted sum by
$$
\Delta C=aD+bd-(ad+bD)=(a-b)(D-d)\leq0.
$$
Fix one chosen weight there, then move the other into the neighbouring deepest position; if it is already there, no exchange is needed. The <prefix code> condition survives because the set of <codewords> is unchanged. Starting from an <optimal prefix code>, the cost cannot decrease below the minimum, so these exchanges preserve optimality. Strictly unequal weights at unequal depths would give a strict decrease, explaining <probability monotonicity of optimal prefix-code lengths>. Equal weights or equal depths allow cost-neutral exchanges. <Symbol Codes by Ben Lynn>{ref}


 Huffman sibling property (source code)