# Tournament Tree Partial Sort

# Tournament Tree Partial Sort

Tournament tree partial sort uses a tournament tree to repeatedly extract the next smallest or largest element. It is useful when only a sorted prefix of length ( k ) is needed.

You use it when you want partial sorted output with predictable comparison structure.

## Problem

Given an array ( A ) of length ( n ) and an integer ( k ), output the smallest ( k ) elements in sorted order without fully sorting all ( n ) elements.

## Idea

A tournament tree stores the winner of comparisons between elements. For smallest ( k ), the winner is the minimum. After outputting the minimum, replace that leaf with infinity and replay only the comparisons along its path to the root.

This avoids rebuilding the structure after every extraction.

## Algorithm

```id="m7x2q8"
tournament_tree_partial_sort(A, k):
    tree = build_min_tournament_tree(A)
    result = []

    repeat k times:
        value, leaf = tree.minimum()
        result.append(value)

        tree.update(leaf, +infinity)

    return result
```

## Example

Input:

[
A = [7, 2, 5, 1, 9, 3]
]

and

[
k = 3
]

The tournament tree first reports ( 1 ). After replacing it with infinity, the tree is repaired and reports ( 2 ), then ( 3 ).

Output:

[
[1, 2, 3]
]

## Correctness

The root of a min tournament tree always stores the smallest active element. Replacing the extracted winner with infinity removes it from future consideration. Updating the path from that leaf to the root restores the tournament invariant.

Repeating this process emits the smallest elements in increasing order.

## Complexity

| phase                   | cost                |
| ----------------------- | ------------------- |
| build tree              | ( O(n) )            |
| each extraction         | ( O(\log n) )       |
| total for ( k ) outputs | ( O(n + k \log n) ) |

Space:

[
O(n)
]

## Comparison with Heap Partial Sort

| method          |    build |       extract k |    space |
| --------------- | -------: | --------------: | -------: |
| heap            | ( O(n) ) | ( O(k \log n) ) | ( O(n) ) |
| tournament tree | ( O(n) ) | ( O(k \log n) ) | ( O(n) ) |

Tournament trees make comparison paths explicit, which can be useful for parallelism, replay, and loser-tree variants.

## When to Use

Use tournament tree partial sort when:

* only the first ( k ) sorted elements are needed
* explicit comparison structure is useful
* repeated minimum or maximum extraction is required
* predictable update paths matter

For memory-constrained top-( k ), a size-( k ) heap is often better.