企业营销管理制度/全网营销与seo

胜者树是一棵完全二叉树，输入全在叶子节点。
直接举个例子说明：

上图中有3路，分别位于节点3、4、5，节点4、5进行比较胜者到节点2，节点2再和节点3比较胜者到节点1，节点1里就是最终的胜者。假如胜者来自节点5，从节点5再取一个新的元素，和节点4进行比较，一直上升到节点1，重复该过程直到3路中都没有元素即完成归并。
下图也是类似。

没找到别人的实现就自己写了个，用数组保存胜者树，实现如下：

template <typename OutputIter, typename IterWrapper, typename Compare>
size_t _Compete(OutputIter& result, std::vector<IterWrapper>& input, Compare&& comp)
{const int N = input.size();IterWrapper** tree = new IterWrapper * [N << 1];int valid = N;int k = N;for (auto& iter : input){if (!iter.Valid()) --valid;iter.SetPos(k);tree[k] = &iter;++k;}if (valid == 0){delete[] tree;return 0;}auto compete = [tree, &comp](int right_child_index){IterWrapper* right = tree[right_child_index];IterWrapper* left = tree[right_child_index - 1];if (!right->Valid()) tree[right_child_index >> 1] = left;else if (!left->Valid()) tree[right_child_index >> 1] = right;else if (comp(**right, **left)) tree[right_child_index >> 1] = right;else tree[right_child_index >> 1] = left;};//build winner treefor (k = 2 * N - 1; k > 1; k -= 2){compete(k);}//弹出胜者，在剩下的中再进行一轮比赛，重复该过程size_t nres = 0;while (true){IterWrapper& winner = *tree[1];*result = *winner;++nres;++result;++winner;if (!winner.Valid()){if (--valid == 0) break;}for (int k = winner.GetPos(); k > 1; k = k >> 1){compete(k | 1);}}delete[] tree;return nres;
}

更完整的代码在 here。