锦标赛排序cppm

// Date:      2026-04-29
// Author:    www.xinweikaoyan.com
// Compiler:  GCC 15.2
// Target:    Ubuntu 24.04.1 LTS (x86_64)
// Standard:  C++26 with modules

export module tournament_sort;
import std;
using Rank = std::size_t;

// 胜者树节点结构
struct Node {
    int value { };   // 存储的值
    Rank rank { };   // 在原始向量中的位置（用于保持稳定性）
    auto operator<=>(const Node&) const = default; // 生成所有比较运算符（先比value，后比rank）
};

void update_parent(std::vector<Node>& tournament_tree, const Rank parent_rank){
    auto [lchild_rank, rchild_rank] = std::pair{ 2 * parent_rank + 1, 2 * parent_rank + 2 };
    tournament_tree[parent_rank] = std::min(tournament_tree[lchild_rank], tournament_tree[rchild_rank]);
}

std::vector<Node> build_tournament_tree(const std::vector<int>& arr, const Rank n) {
    std::vector<Node> tournament_tree(2 * n - 1);
    // 初始化叶子节点
    for (Rank i { 0 }; i < n; i++){
        tournament_tree[n - 1 + i] = {arr[i], i};
    }
    // 初始化分支节点
    for (Rank i { 0 }; i < n - 1; i++) {
        const Rank parent_rank = n - 2 - i;
        update_parent(tournament_tree,parent_rank);
    }
    return tournament_tree;
}

// 锦标赛排序实现
export void tournament_sort(std::vector<int>& arr) {
    const Rank n {arr.size()};
    if (n < 2) return;
    
    std::vector<Node> tournament_tree = build_tournament_tree(arr, n);
    
    // 排序阶段
    for (Rank i { 0 }; i < n; i++) {
        // 当前最小值赋值给arr[i]
        arr[i] = tournament_tree[0].value;       
        // 定位到对应的叶子节点并标记为"淘汰"
        Rank node_rank {tournament_tree[0].rank + n - 1};
        tournament_tree[node_rank].value = std::numeric_limits<int>::max();
        
        // 向上调整胜者树
        while (node_rank > 0) {
            node_rank = (node_rank - 1) / 2; 
            update_parent(tournament_tree, node_rank);
        }
    }
}