y_tfun_tournament.h

二叉树

#if !defined(AFX_Y_CLS_CONTESTSORT_H__FA4AEF06_CB4B_4B37_8B7D_C9A435E94103__INCLUDED_)
#define AFX_Y_CLS_CONTESTSORT_H__FA4AEF06_CB4B_4B37_8B7D_C9A435E94103__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

template<typename T>
class DataNode
{
public:
	T data;		//数据值
	int index;	//在树中的下标
	int active;	//是否还需要比较
	BOOL operator <=(const DataNode<T> &x)
	{
		if(data<=x.data)
			return TRUE;
		else
			return FALSE;
	}
	BOOL operator >=(const DataNode<T> &x)
	{
		if(data>x.data)
			return TRUE;
		else
			return FALSE;
	}
};
//**************************************************//
//函数名  : void TournamentSort(T a[],int n,BOOL bIfAscending = TRUE)
//功能	  : 竞赛排序
//参数	  : T a[]	比较的数组
//			int n	数组个数
//			bIfAscending	是否是升序
//编写人  : 	
//返回值  : 
//备注	  : 竞赛排序
//			N 最后一行完全二叉数中结点个数(N>=n)
//			时间复杂度:	比较次数为O(N*Log2(N))。
//			空间复杂度:	2*N-1(个结点)
//编写日期:	2004-8-26
//**************************************************//	
template<typename T>
void TournamentSort(T a[],int n,BOOL bIfAscending = TRUE)
{
	DataNode<T> * tree;
	DataNode<T> item;
	int bottomRowSize;		//二叉树最后一行的节点个数
	int treesize;			//二叉树中最后一行为bottomRowSize个节点的完全树中结点个数	
	int loadindex;			//最后一层的起始下标
	int i,j;
	int k = (int)(log(n)/log(2)+0.99);	//求二叉树的层数
	bottomRowSize = 1;
	bottomRowSize = bottomRowSize<<k;		

	treesize = 2* bottomRowSize - 1;	//计算树的大小并动态申请其结点
	loadindex = bottomRowSize - 1;
	tree = new DataNode<T>[treesize];
	//copy 数组到DataNode对象的树中
	j = 0;
	for(i = loadindex;i<treesize;i++)
	{
		item.index = i;
		if(j<n)
		{
			item.active = 1;
			item.data = a[j++];
		}
		else
			item.active = 0;
		tree[i] = item;
	}
	//第一次比较找出最小的元素
	i = loadindex;
	while(i>0)
	{
		j = i ;
		while(j<2*i)
		{
		
			if(bIfAscending)
			{
				if(!tree[j+1].active|| tree[j] <= tree[j+1])
					tree[(j-1)/2] = tree[j];
				else
					tree[(j-1)/2] = tree[j+1];
			}
			else
			{
				if(!tree[j+1].active|| tree[j] >= tree[j+1])
					tree[(j-1)/2] = tree[j];
				else
					tree[(j-1)/2] = tree[j+1];
			}
			j +=2;
		}
		//移动到上一层比较本次比赛的优胜者
		i = (i -1)/2;
	}
	//处理其余N-1个元素。将优胜者从根copy到数组中,使其为不活跃。修改树，允许优胜者的对手进入比赛
	for(i = 0 ;i<n - 1;i++)
	{
		a[i] = tree[0].data;
		tree[tree[0].index].active = 0;
		UpdateTree(tree,tree[0].index,bIfAscending);
	}
	//将最大值copy到数组
	a[n - 1] = tree[0].data;
	delete [] tree;
}

template<typename T>
void UpdateTree(DataNode<T> *tree, int i,BOOL bIfAscending)
{
	int j;
	//标注优胜者i的对手。通过将其赋值级双亲结点允许它重新参加比赛
	if(i%2 ==0)
		tree[(i-1)/2] = tree[i-1];	//优胜者对手为左孩子
	else
		tree[(i-1)/2] = tree[i+1];	//优胜者对手为右孩子
	//重新比赛
	i = (i-1)/2;
	while(i>0)
	{
		//位置i的对手为左结点或右节点?
		if(i%2 ==0)
			j = i -1;
		else 
			j = i+1;
		//是否对手为不活跃？
		if(!tree[i].active||!tree[j].active)
			if(tree[i].active)
				tree[(i-1)/2] = tree[i];
			else
				tree[(i-1)/2] = tree[j];
		//将比赛胜都赋给其双亲
		else
			if(bIfAscending)
			{
				if(tree[i]<=tree[j])
					tree[(i-1)/2] = tree[i];
				else
					tree[(i-1)/2] = tree[j];
			}
			else
			{
				if(tree[i]>=tree[j])
					tree[(i-1)/2] = tree[i];
				else
					tree[(i-1)/2] = tree[j];
			}
		//移动上一层比赛
		i = (i-1)/2;
	}
	//本软比赛结束，根节点存放者最大最小值
}


#endif