本文共 1735 字，大约阅读时间需要 5 分钟。
对于对路归并与败者树的概念参见
下面模拟了简单的利用败者树进行多路归并的场景#include#include #include #include using namespace std;//5路归并树const int K = 5;//最小关键字const int MINKEY = -0x3f3f3f3f;//最大关键字const int MAXKEY = -MINKEY;//表示关键字的范围void Adjust(vector &b,vector &ls, int s){ //调整loser树 int t = (s + K)/2; while (t > 0) { if(b[s] > b[ls[t]]) { //交换ls[t] 与 s 的值 ls[t] = s ^ ls[t]; s = s ^ ls[t]; ls[t] = s ^ ls[t]; } t /= 2; } ls[0] = s;}void CreatLoserTree(vector &b,vector &ls){ b[K] = MINKEY; //创建失败树 for(int i = 0; i < ls.size(); i++) { ls[i] = K; } for(int i = K-1; i >= 0; i--) { //调整每一个 Adjust(b,ls,i); }}//多路归并与失败树int main(){ srand((unsigned int)time(NULL)); vector > vec; vector ls; //失败树 vector b; //存放K个关键字 b.resize(K+1); ls.resize(K); //记录总的元素的个数 int count = 0; for(int i = 0; i < K; i++) { vector tmp; for(int j = 0; j < 20; j++) { count++; tmp.push_back(rand() % 100); } //排序 sort(tmp.begin(),tmp.end(),greater ()); vec.push_back(tmp); tmp.clear(); } //初始化b数组，loser树中的数据项 for(int i = 0; i < K; i++) { b[i] = vec[i].back(); vec[i].pop_back(); } //创建loser树 CreatLoserTree(b,ls); vector res; //归并后的结果 //取归并后的结果 while(count > 0) { res.push_back(b[ls[0]]); count--; if(vec[ls[0]].size() == 0) { //如果一个序列变为空，则将该序列对应的loser树的位置置为最大值 b[ls[0]] = MAXKEY; } else { //如果序列不为空，即该序列的还没有归并完，则从序列中取出一个最小值 //加入到loser树中 b[ls[0]] = vec[ls[0]].back(); vec[ls[0]].pop_back(); } Adjust(b,ls,ls[0]); } for(auto val:res) { cout << val << " "; } cout << endl; return 0;}
转载地址：http://yxnwi.baihongyu.com/