Winner/Loser tree

Invented by Demuth (1956)
Idea:
  • a data structure for merging \(k\) sorted runs
  • imagine playing a tournament; at each node we compare the two contestants; we store the loser in the node and the winner proceeds up in the tree
    • the overall winner ends up in one extra slot above the root: the next element of the merge
    • after an extraction, the run's new head must play the ancestors on its way to the root
    • a winner tree stores the winner instead, which is more obvious but forces every replayed match to fetch the sibling node as well
Advantages:
  • exactly \(\lceil\log_2 k\rceil\) comparisons per extracted element; a binary heap over the same \(k\) heads does twice as many in the worst case
  • each of those comparisons reads a single slot, the one it may then overwrite, so a replay never looks off the path — a winner tree must read each ancestor's sibling as well

References

  • H.B. Demuth. Electronic Data Sorting. PhD thesis, Stanford University, 1956.
  • D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, section 5.4.1 (Multiway merging and replacement selection). Addison-Wesley, 2nd edition, 1998.