File LoserTree.h

↰ Parent directory (ADS/priority)

The tree of losers of a tournament among k players, the structure of the merge of k sorted sequences (Knuth 5.4.1; the notes, section 5.1.3, use a heap of k pairs for the same purpose).

Definition (ADS/priority/LoserTree.h)

Detailed Description

The k players are the leaves of a complete binary tree with k - 1 internal nodes, laid out as a heap (the leaf of player i is the node k + i, the parent of node v is v / 2); each internal node keeps the loser of the match played there, and the node 0 keeps the overall winner, the player with the smallest key, the lower index on equal keys, so that a merge through the tree is stable. When the winner gets a new key (the next item of its sequence) or runs out (an exhausted player loses every match), replace() replays only the matches on the path from its leaf to the root, against the losers stored there: exactly :math:` lceil log_2 k rceil ` or :math:` lfloor log_2 k rfloor ` comparisons (a match on equal keys is decided by the indices, with the same single call of less), no more, while a binary heap [see File DaryHeap.h] pays up to :math:` 2 log_2 k ` for its pop and push, since each level of its sift down compares the two children and then the item moved down. The construction plays the k - 1 matches once, O( k ).

kWayMerge() merges k sorted vectors through the tree, :math:` n lceil log_2 k rceil + k ` comparisons at most for n items in all; in the external memory the same merge, fed by one block per sequence, is the step of the multiway mergesort [see File ExternalSorting.h].

The contracts [see File Contract.h]: k >= 1; top() and replace() on a tree whose players are not all exhausted; the invariant, that the winner has a key not larger than that of every player, is checked after each replace(); kWayMerge() needs sorted sequences and gives their items sorted, an audit. The functions are defined in LoserTree.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 5

    1. Knuth, The Art of Computer Programming, vol. 3, 2nd ed., Addison-Wesley, 1998, section 5.4.1

  1. Sanders, Fast priority queues for cached memory, ACM Journal of Experimental Algorithmics 5, 7, 2000, doi:10.1145/351827.384249

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions