多路归并排序和败者树

多路归并排序和败者树 败者树特点

每棵子树的根节点都是当前子树所有节点的亚军，形式上和二叉树近似，和二叉树不一样的地方在于，根节点增加了一个父亲节点用于存储整个子树的冠军。

败者树是完全二叉树，可以使用数组来实现。如在5路归并的实现时，下标2（从0开始计算）对应的父亲节点在败者树中的下标是(2+5)/2。

败者树的根节点会存储整个数组中最小的数（或最大的），对于其到根节点的路径中，存储的都是兄弟树最大值，因此我们在进行比较的时候，可以直接和兄弟树的最大值进行比较，如果胜出那么直接晋级下一轮，否则兄弟节点晋级下一轮，这里巧妙的利用父亲节点存储各个子树的亚军，从而减少了一次对兄弟节点的访问。

和胜者树的比较

胜者树存储的是胜出节点的位置，当树pop并添加新的数据时，无论是向上调整还是向下调整，都要遍历一次树根到叶子节点路径的信息，此外还需要和兄弟节点比较大小，因此访存次数比败者树多了一次。

实现时需要注意的地方

败者树非叶子节点应该初始化为n路数据源中最大值的下标，然后正常调整即可。

实现

#include 
#include 
#include 
#include 
#include 
#include 

void adjust(std::vector &loserTree, std::vector &nodes, int index)
{
    // index is winner, also in initial
    assert(index < nodes.size());
    int father = (index + nodes.size()) / 2;
    while (father > 0)
    {

        if (nodes[loserTree[father]] < nodes[index])
        // if (nodes[index] < nodes[loserTree[father]])
        {
            int tmp = loserTree[father];
            loserTree[father] = index; // parent's node record loser
            index = tmp;               // index is winner
        }
        father /= 2;
    }
    loserTree[0] = index;
}

int main()
{
    std::vector nodes = {5, 9, 3, 1, 9, 10, -1, 100};
    // loserTree's init
    int index = std::distance(nodes.cbegin(), std::min_element(nodes.cbegin(), nodes.cend()));
    // int index = std::distance(nodes.cbegin(), std::max_element(nodes.cbegin(), nodes.cend()));
    std::vector ls(nodes.size(), index);
    for (int i = 0; i < nodes.size(); ++i)
    {
        adjust(ls, nodes, i);
    }

    // sort
    for (int i = 0; i < nodes.size(); ++i)
    {
        std::cout << nodes[ls[0]] << 'n';
        nodes[ls[0]] = INT_MAX;
        // nodes[ls[0]] = INT_MIN;
        adjust(ls, nodes, ls[0]);
    }
}