What does Lazy Tool Hubs conclude, in numbers, about “Building Huffman Trees: Many-Way Merging, Dummy Leaves and the Price of a Menu”?
Answer: A many-way Huffman tree must be padded with dummy leaves first; otherwise a 10-ary tree needs more than a quarter more decisions. On small instances the Huffman tree matched the exhaustive optimum in all 720 cases. Decisions are not tokens: each decision reads a menu, and the best branching factor in tokens is about 2.72 with zero hop cost and about 5.09 with a hop cost of 80 tokens. Yet this chapter has kept avoiding one question. A Huffman tree lumps cold tools together by frequency into a branch, so the model sees on its menu a node without a name. How is it to know that the tool it wants lies down that branch? The next chapter answers this, and puts a price on the answer.
Scope of the numbers: Selection accuracy lacks reliable peer-reviewed primary evidence and is demoted to an author's hypothesis. Marked boxes separate published evidence, runnable Python calculations (17 programs), classical sources and the author's hypotheses.
Data table
The numbers below are printed verbatim by the chapter's Python program and can be reproduced by running it. standard-library Python onlyprinted values that match the answer: 10, 2.72, 5.09, 80
| k | tokens HOP=0 | bound | tokens HOP=80 | bound |
| 2 | 320.3 | 318.6 | 832.7 | 828.4 |
| 3 | 305.2 | 301.5 | 630.7 | 623.2 |
| 4 | 325.1 | 318.6 | 585.1 | 573.5 |
| 5 | 350.9 | 343.0 | 575.4 | 562.6 |
| 6 | 379.9 | 369.8 | 582.5 | 567.0 |
| 8 | 441.4 | 424.8 | 618.0 | 594.7 |
| 10 | 499.3 | 479.6 | 659.0 | 633.0 |
| 16 | 682.6 | 637.2 | 819.1 | 764.7 |
| 32 | 1124.5 | 1019.5 | 1236.9 | 1121.5 |
| flat menu of all 300 one-line entries: 7500 tokens | ||||
| HOP= | 0: continuous optimum k* = 2.72 | |||
| HOP= 80: continuous optimum k* = 5.09 | ||||
| HOP=400: continuous optimum k* = 11.26 |
Show the full program
# Chapter 2. p23: decisions are not tokens; the menu has to be read.
# Each routing decision reads a k-line menu (S tokens a line) and pays
# a fixed hop overhead HOP (call framing, reply envelope). Per lookup
# the router pays (HOP + k S) per decision, so the token bound is
# (HOP + k S) H / log2(k), not H. Shown for HOP = 0 and HOP = 80, with
# the padded k-ary Huffman tree on N = 300 Zipf(1) tools. The real
# optimum k solves k (ln k - 1) = HOP / S. S, HOP are illustrative.
import heapq
import math
N, S = 300, 25
def zipf(n, a):
w = [1.0 / (i ** a) for i in range(1, n + 1)]
t = math.fsum(w)
return [x / t for x in w]
def entropy(p):
return -math.fsum(x * math.log2(x) for x in p if x > 0)
def huff_l(p, k):
items = [(x, i, (i,)) for i, x in enumerate(p)]
seq, pad = len(p), 0
while k > 2 and (len(items) + pad - 1) % (k - 1):
pad += 1
for _ in range(pad):
items.append((0.0, seq, ()))
seq += 1
heapq.heapify(items)
depth = [0] * len(p)
while len(items) > 1:
kids = [heapq.heappop(items) for _ in range(min(k, len(items)))]
leaves = ()
for c in kids:
for i in c[2]:
depth[i] += 1
leaves += c[2]
heapq.heappush(items, (math.fsum(c[0] for c in kids), seq, leaves))
seq += 1
return math.fsum(x * d for x, d in zip(p, depth))
def k_star(ratio):
lo, hi = 1.0001, 1000.0
for _ in range(200):
mid = (lo + hi) / 2
if mid * (math.log(mid) - 1) < ratio:
lo = mid
else:
hi = mid
return lo
p = zipf(N, 1.0)
h = entropy(p)
print(" k tokens HOP=0 bound tokens HOP=80 bound")
for k in (2, 3, 4, 5, 6, 8, 10, 16, 32):
lk = huff_l(p, k)
b = h / math.log2(k)
print("%3d %10.1f %8.1f %12.1f %8.1f"
% (k, lk * k * S, b * k * S, lk * (80 + k * S),
b * (80 + k * S)))
print("flat menu of all %d one-line entries: %d tokens" % (N, N * S))
for hop in (0, 80, 400):
print("HOP=%3d: continuous optimum k* = %.2f" % (hop, k_star(hop / S)))Single source and citation
Fan, Y. (2026). A Lazy-Loading Private Tool Hub: Near-Zero Opening Context for Hundreds of Checkers and On-Demand Routing Trees (Version 1.0.0), Chapter 2: Building Huffman Trees: Many-Way Merging, Dummy Leaves and the Price of a Menu. 5D Library. DOI pending
DOI pending · monograph page goes live after publication · 5DL-B-257 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026257,
author = {Fan, Yafu},
title = {A Lazy-Loading Private Tool Hub: Near-Zero Opening Context for Hundreds of Checkers and On-Demand Routing Trees},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
note = {DOI pending}
}Other chapter answers in this book
- Chapter 1 · The Linear Bill: Context Cost of Loading Everything and the Entropy Bound
- Chapter 3 · Navigable Trees: the Price of Alphabetic Order and the Accumulation of Wrong Turns
- Chapter 4 · The Branching Factor: Depth against Width, and Hanging Popular Tools on the Root
- Chapter 5 · Queueing with Cold Starts: the Delay Bill of Lazy Loading and How Long to Stay Warm
- Chapter 6 · Frequency Drift: the Cost of Wrong Frequencies and When to Rebuild the Routing Tree
- Chapter 7 · Classical Sources East and West: Offices and Duties in the Rites of Zhou and Dewey's Decimal Scheme
- Chapter 8 · Closing the Loop: a Monthly Report on Catalogue Layering and Call Frequency