采用堆的多路归并
一些思索：为什么是C ，而不是C++ —— 理想和现实的博弈。
Jun
23
坦白说，我不确定这个东西是不是叫做败者树，因为我觉得它就是以前写过n遍的线段树的一个简单变种。
在线段树的每个节点存储v, i，分别表示该区间内最小值和最小值所在单元的索引。
建立好线段树以后，每次取出整个区间的最小值，然后将该值来源的那一路的下一个数字填充进去
如果那一路已经没有下一个数字了，就填一个max进去，然后递归地更新其所有祖先节点。
这个过程有点像heap的sift_up。
代码如下:
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
在线段树的每个节点存储v, i，分别表示该区间内最小值和最小值所在单元的索引。
建立好线段树以后，每次取出整个区间的最小值，然后将该值来源的那一路的下一个数字填充进去
如果那一路已经没有下一个数字了，就填一个max进去，然后递归地更新其所有祖先节点。
这个过程有点像heap的sift_up。
代码如下:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct node_t{
int l, r, v, i;
};
node_t d[1024];
int n;
int a[][5] = {
{7,8,10,13,14},
{0,3,6,12,19},
{2,4,5,7,10},
{15,17,19,21,23},
{5,8,9,20,22}
};
int idx[5] = {1,1,1,1,1};
void make(int l, int r, int i = 1){
if(l > r) return;
int m = (l + r) / 2;
/*
printf("[%d, %d, %d] @ %d, ", l, m, r, i);
if(l == r) printf("%d", a[l][0]);
printf("\n");
*/
d[i].l = l, d[i].r = r;
if(l < r){
make(l, m, 2 * i);
make(m + 1, r, 2 * i + 1);
if(d[2*i].v < d[2*i+1].v){
d[i].v = d[2*i].v;
d[i].i = d[2*i].i;
}else{
d[i].v = d[2*i + 1].v;
d[i].i = d[2*i+1].i;
}
}else if(l == r){
d[i].v = a[l][0];
d[i].i = i;
}
}
void dump(int i = 1, int dep = 0){
for (int j = 0; j < dep; ++j) printf(" ");
printf("[%d, %d] @ %d (%d @ %d)\n", d[i].l, d[i].r, i, d[i].v, d[i].i);
if(d[i].l < d[i].r) {
dump(2*i, dep+1);
dump(2*i+1, dep+1);
}
}
int main(){
make(0, 4);
dump();
int cnt = 0;
while(cnt < 25){
int t = d[1].i;
int i = d[t].l;
printf("%2d @ %d FROM %d\n", d[t].v, d[t].i, i);
if(idx[i] < 5){
d[t].v = a[i][idx[i]++];
}else{
//printf("QUEUE %d OVER\n", i);
d[t].v = 1000000;
}
while(t > 1){
t /= 2;
if(d[2*t].v < d[2*t+1].v){
d[t].v = d[2*t].v;
d[t].i = d[2*t].i;
}else{
d[t].v = d[2*t + 1].v;
d[t].i = d[2*t+1].i;
}
}
cnt++;
}
return 0;
}
#include <algorithm>
#include <cstring>
using namespace std;
struct node_t{
int l, r, v, i;
};
node_t d[1024];
int n;
int a[][5] = {
{7,8,10,13,14},
{0,3,6,12,19},
{2,4,5,7,10},
{15,17,19,21,23},
{5,8,9,20,22}
};
int idx[5] = {1,1,1,1,1};
void make(int l, int r, int i = 1){
if(l > r) return;
int m = (l + r) / 2;
/*
printf("[%d, %d, %d] @ %d, ", l, m, r, i);
if(l == r) printf("%d", a[l][0]);
printf("\n");
*/
d[i].l = l, d[i].r = r;
if(l < r){
make(l, m, 2 * i);
make(m + 1, r, 2 * i + 1);
if(d[2*i].v < d[2*i+1].v){
d[i].v = d[2*i].v;
d[i].i = d[2*i].i;
}else{
d[i].v = d[2*i + 1].v;
d[i].i = d[2*i+1].i;
}
}else if(l == r){
d[i].v = a[l][0];
d[i].i = i;
}
}
void dump(int i = 1, int dep = 0){
for (int j = 0; j < dep; ++j) printf(" ");
printf("[%d, %d] @ %d (%d @ %d)\n", d[i].l, d[i].r, i, d[i].v, d[i].i);
if(d[i].l < d[i].r) {
dump(2*i, dep+1);
dump(2*i+1, dep+1);
}
}
int main(){
make(0, 4);
dump();
int cnt = 0;
while(cnt < 25){
int t = d[1].i;
int i = d[t].l;
printf("%2d @ %d FROM %d\n", d[t].v, d[t].i, i);
if(idx[i] < 5){
d[t].v = a[i][idx[i]++];
}else{
//printf("QUEUE %d OVER\n", i);
d[t].v = 1000000;
}
while(t > 1){
t /= 2;
if(d[2*t].v < d[2*t+1].v){
d[t].v = d[2*t].v;
d[t].i = d[2*t].i;
}else{
d[t].v = d[2*t + 1].v;
d[t].i = d[2*t+1].i;
}
}
cnt++;
}
return 0;
}
欢迎扫码关注：
转载请注明出自 ，如是转载文则注明原出处，谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php 。
