在树形选择排序中，利用锦标赛思想建立的树称为胜者树。
1、每个非终端节点存储的是左右孩子节点中的优胜者。
2、通过减少比较次数，提高效率。
3、胜者树就是一颗特殊的线段树。
一、构建树
Procedure buildmint; 复杂度 O(n)
var i,j,k:longint;
begin
i:=N; j:=N+n-; { 其中 N 为大于等于 n 的最小 2 次方数 }
while i> do
begin
k:=i;
while k
begin
f[k div ]:=min(f[k],f[k+]);
k:=k+;
end;
if j and = then f[j div ]:=f[j];
i:=i div ; j:=j div ;
end;
end;
二、查询
核心思想：自下向上，奇偶缩进。
Function findmin(x,y:longint):longint; 复杂度 O(logn)
var i,j,k,r:longint;
begin
i:=x+N-; j:=y+N-; r:=i;
while i<=j do
begin
if (f[r]>f[i]) then r:=i;
if (f[r]>f[j]) then r:=j;
if (i and =) then inc(i);
if (j and =) then dec(j);
i:=i shr ; j:=j shr ;
end; exit(f[r]);
while r
if (f[r]=f[r*]) then r:=r* else r:=r*+;
exit(r-N+);
end;
三、更新
核心思想：自下而上，更新父节点。
胜者树不擅长更新，因为，某个结点更新的时候，它还需要跟兄弟结点比较。更新频繁的情况，用败者树。
四、败者树
败者树是胜者树的一种变体。在败者树中，用父结点记录其左右子结点进行比赛的败者，而让胜者参加下一轮的比赛。败者树的根结点记录的是败者，需要加一个结点来记录整个比赛的胜利者。采用败者树可以简化重构的过程。
典型应用：多路归并排序，可以减少比较次数。
五、代码实现胜者树
Description
An array of size n ≤ 106 is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:
The array is [1 3 -1 -3 5 3 6 7], and k is 3.
Window position
Minimum value
Maximum value
[1 3 -1] -3 5 3 6 7
-1
3
1 [3 -1 -3] 5 3 6 7
-3
3
1 3 [-1 -3 5] 3 6 7
-3
5
1 3 -1 [-3 5 3] 6 7
-3
5
1 3 -1 -3 [5 3 6] 7
3
6
1 3 -1 -3 5 [3 6 7]
3
7
Your task is to determine the maximum and minimum values in the sliding window at each position.
Input
The input consists of two lines. The first line contains two integers n and k which are the lengths of the array and the sliding window. There are n integers in the second line.
Output
There are two lines in the output. The first line gives the minimum values in the window at each position, from left to right, respectively. The second line gives the maximum values.
Sample Input
8 3
1 3 -1 -3 5 3 6 7
Sample Output
-1 -3 -3 -3 3 3
3 3 5 5 6 7
Source
#include
#include
using namespace std;
const int MX = ;
int n, k;
int a[MX], minRes[MX], maxRes[MX];
int treeMin[*MX], treeMax[*MX];
int N;
//构建一颗winner tree，tree用数组存储，根结点是数组的第二个结点，即A[1]
//叶子结点是原始数组。树的最左结点的下标是2的指数
void build() {
int i = N, j = N+n-;
while (i > ) {
int t = i;
while (t < j) {
treeMin[t/] = min(treeMin[t], treeMin[t+]);
treeMax[t/] = max(treeMax[t], treeMax[t+]);
t += ;
}
if ((j&) == ) {//下标j是偶数，说明这个结点是落单的
treeMin[j/] = treeMin[j];
treeMax[j/] = treeMax[j];
}
i = i>>;
j = j>>;
}
}
int query(int x, int y) {
int i=x+N, j=y+N, t = i;
while (i <= j) {
if (treeMin[t] > treeMin[i]) t = i;
if (treeMin[t] > treeMin[j]) t = j;
if ((i&) == ) i++;
if ((j&) == ) j–;
i = i>>;
j = j>>;
}
//return treeMin[t];
while (t < N) {
if (treeMin[t] == treeMin[t*]) t = t*;
else t = t*+;
}
return treeMin[t];
//return t – N;
}
void work() {
for (int i=; i
int x=N+i, y=x+k-, t=x, r=x;
while (x<=y) {
if (treeMin[t] > treeMin[x]) t = x;
if (treeMin[t] > treeMin[y]) t = y;
if (treeMax[r] < treeMax[x]) r = x;
if (treeMax[r] < treeMax[y]) r = y;
if ((x&) == ) x++;
if ((y&) == ) y–;
x = x>>;
y = y>>;
}
minRes[i] = treeMin[t];
maxRes[i] = treeMax[r];
}
}
void printRes() {
for (int i=; i
if (i!=) cout<
cout<
}
cout<
for (int i=; i
if (i!=) cout<
cout<< maxRes[i];
}
cout<
}
int calN(int x) {
int i = ;
while (i < x) {
i = i<
}
return i;
}
void printTree() {
cout << “min winner tree:” << endl;
for (int i=; i< n+N; i++) {
cout << treeMin[i] << ” “;
}
cout << endl << “max winner tree:” << endl;
for (int i=; i
cout << treeMax[i] << ” “;
}
cout << endl;
}
int main()
{
cin >> n >> k;
N = calN(n);
for (int i=; i
cin >> a[i];
treeMax[N+i] = treeMin[N+i] = a[i];
}
build();
//printTree();
work();
printRes();
//cout<
//cout << “Hello world!” << endl;
return ;
}
Mysql存储引擎之TokuDB以及它的数据结构Fractal tree(分形树)
在目前的Mysql数据库中,使用最广泛的是innodb存储引擎.innodb确实是个很不错的存储引擎,就连高性能Mysql里都说了,如果不是有什么很特别的要求,innodb就是最好的选择.当然,这偏文 …
页面设计–Tree目录树
Tree目录树控件属性: 根据数据集合来配置相应的信息 加载模式有自动加载.自定加载 web中显示效果图:
[转] Splay Tree(伸展树)
好久没写过了,比赛的时候就调了一个小时,差点悲剧,重新复习一下,觉得这个写的很不错.转自:here Splay Tree(伸展树) 二叉查找树(Binary Search Tree)能够支持多种动态集 …
CJOJ 1976 二叉苹果树 / URAL 1018 Binary Apple Tree(树型动态规划)
CJOJ 1976 二叉苹果树 / URAL 1018 Binary Apple Tree(树型动态规划) Description 有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的 …
【数据结构】B-Tree, B+Tree, B*树介绍 转
[数据结构]B-Tree, B+Tree, B*树介绍 [摘要] 最近在看Mysql的存储引擎中索引的优化,神马是索引,支持啥索引.全是浮云,目前Mysql的MyISAM和InnoDB都支持B-Tre …
poj 1741 Tree(树的点分治)
poj 1741 Tree(树的点分治) 给出一个n个结点的树和一个整数k,问有多少个距离不超过k的点对. 首先对于一个树中的点对,要么经过根结点,要么不经过.所以我们可以把经过根节点的符合点对统计出 …
【POJ 2486】 Apple Tree(树型dp)
[POJ 2486] Apple Tree(树型dp) Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8981 Acce …
C++胜者树
#include #define MAX_VALUE 0x7fffffff using namespace std; //在这里我先反思一下.不知道怎么搞的,这个算法 …
MYSQL的B+Tree索引树高度如何计算
前一段被问到一个平时没有关注到有关于MYSQL索引相关的问题点,被问到一个表有3000万记录,假如有一列占8位字节的字段,根据这一列建索引的话索引树的高度是多少? 这一问当时就被问蒙了,平时这也只关注 …
随机推荐
ios中@class和 #import区别
很多刚开始学习iOS开发的同学可能在看别人的代码的时候会发现有部分#import操作写在m文件中,而h文件仅仅使用@class进行声明,不禁纳闷起来,为什么不直接把#import放到h文件中呢?这是因 …
Linux的管道
一.管道是什么? 管道,顾名思义就是个管子,里面可以流过去很多东西.举个栗子 ls | morels输出列出来的文件目录就通过‘|’这个管道流向了more这个文本浏览器.相同的功能我们也可以通过ls …
Django中如何使用django-celery完成异步任务2(转)
原文链接: http://www.weiguda.com/blog/74/ 在上一篇博文中, 我们介绍了如何在开发环境中使用Celery. 接下来我们介绍一下如何在部署环境使用Celery. 1. 简 …
Timer定时器
try { mTimerGoOut = new Timer(); SimpleDateFormat sdf3 = new SimpleDateFormat(“yyyy-MM-dd” …
更新 requests 包之后报 has no attribute &#39;__getitem__&#39; 的错
翻代码的时候看到段一年多前用 python 写的下载图片站图片的代码. 测试下看还能不能下到图片,结果发现跑不起来了,报了个如下的错误: TypeError: ‘instancemethod’ obj …
uva 10391 Compound Words <;set>;
Compound Words You are to find all the two-word compound words in a dictionary. A two-word compound …
web实现QQ第三方登录
开放平台-web实现QQ第三方登录 应用场景 web应用通过QQ登录授权实现第三方登录. 操作步骤 1 注册成为QQ互联平台开发者,http://connect.qq.com …
session.go
package { so.ttl = ttl } } } // WithContext assigns a context to the session …
CMake 笔记
1. configure_file configure_file()让你可以在代码文件中使用CMake中定义的变量. configure_file(
使用 letter-space 后文字不能居中解决
letter-space:2em; text-align: center; 使用letter-space后和上面的字体对比明显没有居中: 选定元素后发现,每个字后面都被加了2em,不是不能居中而是因为 …