4.33

Idea: keep at most [math]k[/math] distinct keys in a balanced binary-search tree (BST) and store for every key how many times it occurs.

Algorithm:
make an empty balanced BST T for each a in input: if a in T: T[a].count += 1 else: insert a with count = 1 output all keys of T by an in-order traversal, printing each key T[key].count times
Correctness: • The in-order traversal of a BST visits keys in ascending order, so the produced sequence is sorted. • Each input element appears exactly once in the multiset represented by the counts, and we output each key precisely its stored number of times, hence every original element is emitted.

Complexity: • The BST never contains more than [math]k[/math] nodes, so one insertion or counter-increment costs [math]O(\log k)[/math]. • Processing all [math]n[/math] numbers therefore costs [math]O(n\log k)[/math]. • The final in-order traversal touches each node once and writes a total of [math]n[/math] values, adding [math]O(n+k)[/math], which is dominated by the insertions. Thus the whole procedure runs in [math]O(n\log k)[/math] time; when [math]k\ll n[/math] this is asymptotically faster than the usual [math]O(n\log n)[/math] comparison sort bound.

Back to Chapter 4