Lost

 左偏树可能各个方面都是最优的，可能他的最大缺点是插入操作O(n)，但是综合并操作与代码难度考虑还是不错的选择

至于他的已知节点删除和变种没实现，待以后用的话再补上吧，觉得几乎没用处？（不敢说XD...

/****************************************
*                 LeftHeap.h
*		Describe: 可并优先队列——左偏树
*       Created: 2010-5-27
*       CopyRight  2010,Leek
*
******************************************/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef int Type;

typedef struct LNode
{
	Type key;
	int dis;
	LNode *left;
	LNode *right;
	LNode (Type key)
	{
		dis = 0;
		left = NULL;
		right = NULL;
		this->key = key;
	}
}LNode;
typedef LNode *PLNode;


void Swap (int &a, int &b)
{
	a ^= b, b ^= a, a ^= b;
}


void Swap (PLNode &a, PLNode &b)
{
	PLNode tmp = a;
	a = b, b = tmp;
}




PLNode LHeap_Merge (PLNode a,PLNode b)
{
	if (a == NULL)
		return b;
	if (b == NULL)
		return a;
	if (a->key > b->key)
		Swap (a->key,b->key);
	a->right = LHeap_Merge (a->right, b);
	if (a->left == NULL || a->right->dis > a->left->dis)
		Swap (a->right,a->left);
	if (a->right == NULL)
		a->dis = 0;
	else
		a->dis = a->right->dis + 1;
	return a;
}

PLNode LHeap_Build (queue<PLNode> &a)
{
	PLNode tmp = a.front();
	while (a.size() > 1)
	{
		a.pop();
		tmp = LHeap_Merge (tmp,a.front());
		a.push(tmp);
		a.pop();
		tmp = a.front();
	}
	return a.front();
}


PLNode LHeap_Insert (Type key,PLNode root)
{
	PLNode tmp = new LNode(key);
	return LHeap_Merge (tmp,root);
}

Type LHeap_Delete_Min (PLNode &root)
{
	PLNode tmp = root;
	root = LHeap_Merge (root->left, root->right);
	Type top = tmp->key;
	delete tmp;
	return top;
}

觉得建树和并操作值得思考多少有点启发性吧

顺便贴上败者树的模板  今天复习结束看漫画去

/****************************************
*                 Loser.h
*		Describe: 败者树
*       Created: 2010-5-27
*       CopyRight  2010,Leek
*
******************************************/
#include <iostream>
using namespace std;

const int N = 1 << 16; //N大于n，并为2的次方
const int n = 234;
typedef int Type;
Type f[N * 2];
Type a[n];
void BuildTree (int n, int f[2 * N])
//建树a存在f N-N+n
{
	memcpy (f + N,a,sizeof (a[0]) *n);
	for (int i = N,j = N + n - 1; i > 1;i >>= 1,j >>= 1)
	{
		for (int k = i; k < j;k += 2)
			f[k >> 1] = f[k] > f[k + 1] ? f[k] : f[k + 1];
		//求得是最大值，可改为最小值
		if (!(j&1))
			f[j >> 1] = f[j];
	}
}

int findmax (int s, int t)
//查询s t中的最大  最小值 
{
	int r = f[s] >= f[t]? s: t;
	for (int i = s,j = t; i < j; i >>= 1, j >>= 1)
	{
		if (!(i & 1) && i + 1 < j && f[i + 1] > f[r])
			r = i + 1;
		if ((j & 1) && j - 1 > i && f[j - 1] > f[r])
			r = j - 1;
	}
	return f[r];
	//以下程序可求a【s t】最大最小值的下标
	while (r < N)
		if (f[r] == f[r << 1])
			r <<= 1;
		else
			if (f[r] == f[(r << 1) + 1])
				r = (r << 1) + 1;
}