A Winner Loser Tree is a specialized data structure that is typically used in sorting and merging algorithms, particularly in scenarios like external sorting or multiway merges. The concept is derived from tournament trees, which are a form of binary tree.

A Winner Loser Tree is a complete binary tree.

It has internal nodes and leaf nodes. The leaf nodes usually represent the elements being merged or sorted (like the heads of sorted arrays in multiway merging).

The tree is essentially a tournament where each internal node represents a match between two elements (the children nodes). In each match (internal node), one element is the “winner” (the smaller or larger one, depending on whether the goal is to sort in ascending or descending order), and the other is the “loser”. And the internal node always keeps the “lower”.

And we need to record the final “winner” additionally (outside of the tree).

private: const Cmp _cmp; constsize_t _size; // Stores the actual leaf nodes. std::vector<int32_t> _leaves; // Stores the internal nodes (winners or losers) of the tree, which is actually the indexes of the leaf nodes. // Each internal node store the loser of its children. std::vector<size_t> _lower_tree; // Store the final winner, which is the index of the leaf nodes. size_t _winner;

void _adjust(size_t leaf) { // For a complete binary tree, the leaf size is power of two, we have `_size - 1` internal nodes, // And here, the leaf nodes and internal nodes are separately stored. So the actual index of the leaf node in the // tree should be `leaf + (_size - 1)`, so the parent should be `(leaf + (_size - 1) - 1) / 2` // // For a non-complete binary tree, the formula still works, but I can't prove it here. size_t parent = (leaf + (_size - 1) - 1) / 2; while (true) { if (leaf < _size && (_lower_tree[parent] == _size || !_cmp(_leaves[leaf], _leaves[_lower_tree[parent]]))) { std::swap(leaf, _lower_tree[parent]); } if (parent == 0) { break; } parent = (parent - 1) / 2; } _winner = leaf; }