TAOCP 5.2.3 Exercise 28

A **ternary heap** is a complete ternary tree stored in an array `A[1.

taocpmathematicsalgorithmsvolume-3hard

Section 5.2.3: Sorting by Selection

Exercise 28. [35] Explore the idea of ternary heaps, based on complete ternary trees instead of binary trees. Do ternary heaps sort faster than binary heaps?

Verified: no
Solve time: 13m24s

Setup

A ternary heap is a complete ternary tree stored in an array A[1..N].
The children of node i are at positions

[ 3i-1,\quad 3i,\quad 3i+1 \qquad (\text{provided they are } \le N), ]

and the parent of node j (j>1) is

[ \left\lfloor \frac{j+1}{3} \right\rfloor . ]

The heap condition is

[ A\bigl\lfloor\tfrac{j+1}{3}\bigr\rfloor \ge A[j] \qquad \text{for } 1 < j \le N . ]

The siftup operation (moving an element down from the root to its proper place) is the ternary analogue of Knuth’s Algorithm H. Given a heap of size r and starting at k = 1:

while k has at least one child ≤ r:
    let c be the child of k with the largest key
    if A[k] < A[c]:
        swap A[k] and A[c]
        k = c
    else:
        break

At a node with m children (m ∈ {1,2,3}), finding the maximum child requires m-1 comparisons; comparing the node with that child adds one more. Hence the number of comparisons at that node equals m.

Solution

Worst‑case comparisons

For a full ternary tree of height h we have N = (3^{h+1}-1)/2. Every internal node has exactly three children, so each level visited during a siftup from the root costs 3 comparisons. The maximum number of levels is h, therefore

[ C_{\text{worst}}^{\text{(ternary)}} = 3h = 3\log_3(2N+1) - 3 ;\sim; 3\log_3 N . ]

For a binary heap the worst‑case is 2\log_2 N. The ratio is

[ \frac{3\log_3 N}{2\log_2 N} = \frac{3}{2}\cdot\frac{\ln 2}{\ln 3} \approx 0.946 < 1 , ]

so ternary heaps already win in the worst case by about 5%.

Average‑case comparisons (sorting phase)

Heapsort consists of building the heap and then repeatedly extracting the maximum. The extraction phase performs N-1 siftup operations on heaps of size r = N-1, N-2, …, 1.
Following Knuth’s analysis for binary heaps (Exercises 25, 26), one shows that for a random d‑ary heap of size r the expected number of levels visited when sifting up the root is \log_d r + O(1), and at each visited internal node (which typically has d children) exactly d comparisons are made. Hence the expected cost of one siftup is d\log_d r + O(1).

Summing over the sorting phase gives

[ C_{\text{sort}} = \sum_{r=1}^{N} \bigl(d\log_d r + O(1)\bigr) = d,N\log_d N - \frac{d}{\ln d},N + O(\log N) . ]

For binary heaps (d=2) the leading coefficient is 2/\ln 2 ≈ 2.8854; for ternary heaps (d=3) it is 3/\ln 3 ≈ 2.7307. Since 3/\ln 3 < 2/\ln 2, ternary heapsort uses asymptotically fewer comparisons (by about 5.4%).

Heap construction

Building the heap by sifting up all internal nodes from bottom to top costs O(N) comparisons. For a full ternary tree the total is at most

[ \sum_{d=0}^{h-1} 3^d \cdot 3(h-d) = 3\cdot 3^h \sum_{j=1}^h \frac{j}{3^j} \sim \frac{3}{2},N , ]

while binary heap construction takes at most 2N. Thus the construction phase is also cheaper for ternary heaps.

Number of moves (exchanges)

Every level visited during a siftup corresponds to one exchange. The expected number of levels is \log_d r + O(1), so the total moves are \sim N\log_d N. For d=3 this is N\log_3 N \approx 0.6309\, N\log_2 N, a 37% reduction compared to binary heaps.

Optimal arity

The leading comparison coefficient for d‑ary heapsort is f(d) = d/\ln d.
f'(d) = (\ln d - 1)/(\ln d)^2 vanishes at d = e ≈ 2.718, and f''(e) > 0. Hence the minimum over integers is at d = 3. Ternary heaps are therefore the optimal integer‑arity heaps.

Conclusion: Ternary heaps sort faster than binary heaps. They require fewer comparisons (by a constant factor ≈ 5%) and substantially fewer moves (≈ 37% fewer), while retaining the same O(N\log N) asymptotic complexity.

Verification

  1. Leading constant check:
    The function f(d) = d/\ln d has derivative f'(d) = (\ln d - 1)/(\ln d)^2.
    f'(2) < 0, f'(3) > 0 ⇒ minimum at d = e ≈ 2.718.
    f(2) = 2/\ln 2 ≈ 2.8854, f(3) = 3/\ln 3 ≈ 2.7307, f(4) = 4/\ln 4 = 2/\ln 2.
    Hence d=3 is the unique integer minimiser.

  2. Boundary cases:

    • N=1,2: both use 0 or 1 comparison, no difference.
    • N=3: binary and ternary both have root with 2 children → 2 comparisons worst case.
    • N=4: ternary heap has height 1 (root with 3 leaves) → 3 comparisons worst case; binary heap has height 2 → 4 comparisons. Ternary wins.

  3. Integral approximation:
    \sum_{r=1}^N \log_3 r = N\log_3 N - N/\ln 3 + O(\log N) by Euler-Maclaurin. Multiplying by 3 gives the claimed leading term. The same for binary with factor 2.

All derivations are consistent and the conclusion holds for all sufficiently large N. ∎

Notes

The improvement is a constant factor; the O(N\log N) complexity is unchanged. In practice, ternary heapsort may be slightly faster due to better cache behaviour (shorter tree) and fewer data moves, though the index calculations involve multiplication by 3 instead of bit shifts. On modern processors the difference is often small, but theoretically ternary heaps are the optimal choice among d‑ary heaps for comparison‑based sorting.