wintree.cpp

赢者树数据结构

#include<iostream>
#include<string>
using namespace std;
const int MAXINT = 65535;
int WA[][5] = {
	{23,89,100,1123,MAXINT},
	{12,20,26,120,MAXINT},
	{56,99,200,263,MAXINT},
	{2,45,111,253,MAXINT}
};
struct WTNode
{
	int key;
	int *p;
};
class WinTree
{
public:
	WinTree(int);
	~WinTree();
	void BuildTree();
	bool getMinKey(int&);

private:
	int getKey(int);
	int getIndex(int);
	void Updata();
	void Initialize();
private:
	int nBufIndex;
	int k;
	WTNode *buf;
	int *l;
};
WinTree::WinTree(int num)
{
	k = num;
	buf = NULL;
	l = NULL;
}
WinTree::~WinTree()
{
	delete[] buf;
	delete[] l;
}
void WinTree::Initialize()
{
	int i;
	buf = new WTNode[k];
	l = new int[k];
	for(i = 0; i < k; i++)
	{
		buf[i].p = WA[i];
		buf[i].key = *(WA[i]);
	}
}
int WinTree::getIndex(int i)
{
	return ((i < k) ? l[i] : i - k);
}
int WinTree::getKey(int i)
{
	return((i < k) ? buf[l[i]].key : buf[i - k].key);
}
void WinTree::BuildTree()
{
	int i;
	Initialize();
	for(i = k - 1; i > 0; i--)
	{
		if(getKey(2*i) > getKey(2*i+1))
			l[i] = getIndex(2*i+1);
		else
			l[i] = getIndex(2*i);		
	}
}
bool WinTree::getMinKey(int& nData)
{
	if(buf[l[1]].key != MAXINT)
	{
		nData = buf[l[1]].key;
		nBufIndex = l[1];
		Updata();
		return true;
	}
	else
	{
		return false;
	}	
}
void WinTree::Updata()
{
	int brother1;
	int brother2, parent;
	buf[nBufIndex].p++;
	buf[nBufIndex].key = *(buf[nBufIndex].p);

	brother1 = nBufIndex + k;
	brother2 = (brother1 % 2 == 0) ? (brother1 + 1) : (brother1 - 1);
	parent = (brother1 + brother2) / 4;
	while(brother1 != 1)
	{
		if(getKey(brother1) > getKey(brother2))
		{
			l[parent] = getIndex(brother2);
		}
		else
		{
			l[parent] = getIndex(brother1);
		}
		brother1 = parent;
		brother2 = (brother1 % 2 == 0) ? (brother1 + 1) : (brother1 - 1);
		parent = (brother1 + brother2) / 4;
	}

}
void main() 
{   
	WinTree wt(4);
	wt.BuildTree();
	int ndata;
	while(wt.getMinKey(ndata))
	{
		cout<<ndata<<endl;
	}
}