首先来说一下什么是左式堆：
A：左式堆是专门用来解优先队列合并的麻烦（任意二叉堆的合并都必须重新合并，O（N）的时间）。
左式堆的性质：
1.定义零路经长：节点从没有两个两个儿子节点的路经长，把NULL定义为-1
2.堆性性质（x的键值比x左右两个儿子节点的键值要大或者要小）
3.堆中的每一个节点x，左儿子的零路经长至少与右儿子的零路经长一样长。
4.节点的距离等于右节点的距离+1.
引理：
若左式堆的距离定义为一定值，则节点数最少的左式堆是完全二叉堆。
定理：
若左式堆的距离为k，则这棵树最少有2^(k+1)-1个节点（由引理推出）
B：左式堆的特殊操作：（Merge）
左式堆一般以结构体定义，结构体要有3个区域：键值区，零路经长区，左右节点区
左式堆和二叉堆的其他操作都是类似的，但是其核心操作都是围绕Merge展开的。
Merge例程：
LEFTIST_NODE *Merge1(LEFTIST_NODE *const s1, LEFTIST_NODE *const s2)//以最小堆为例
{
if (s1->left == NULL) s1->left = s2;
else
{
s1->right = Merge2(s1->right, s2);
if (s1->left->zeroh < s1->right->zeroh)//如果违反零节点定理，我们交换节点
{
LEFTIST_NODE *tmp = s1->left;
s1->left = s1->right; s1->right = tmp;
}
s1->zeroh = s1->right->zeroh + ;//因为这个时候右节点的零节点路经长总是小于左节点的,零点路径长总是取最小的
}
return s1;
} LEFTIST_NODE *Merge2(LEFTIST_NODE *const s1, LEFTIST_NODE *const s2)
{
if (s1 == NULL)
return s2;
else if (s2 == NULL)
return s1;
else if (s1->elements < s2->elements)
return Merge1(s1, s2);
else//s1->elements < s2->elements
return Merge1(s2, s1);
}
有了Merge，一切都变得很简单了
Insert操作：把Insert的值单独列为一个新的节点，然后Merge即可。
DeleteMin（Max）操作：把根节点的左右子堆合并，并且清除根节点。
C：左式堆的应用，数字序列（就是POJ 3666）
POJ 3666那题，可以用左式堆来做。（这一题只用求不下降序列）
那么怎么做呢？这一题可以这么思考：
我们把泥土划分为一个一个区间：比如[q[i]-q[i+1]-1]，[q[i+1],q[i+2]-2]....这样的话，每一个区间的最小价值，就是区间内的所有值改为该区间的中位数，每个区间的中位数是上升的，即可
不过这样说有点先入为主了，我们想一下这样做为什么对。
其实也用不着多严格的证明，我们可以这样看
我们来看这样一个图，假设一个区间的数的分布就是这样的，其实这个价值点就是到任意蓝色轴的距离，那么这个区间所有点的最小值什么时候到最小？没错，就是到中点的时候。
把这个结论推广到全序列，那就是保证当每个区间的中位数是递增的，然后最小值就是对应区间的数变成对应中位数所需要的价值之和。
那么怎么编程呢？左式堆简直就是为这一题设的！
我们可以弄一个这样的堆，堆的最大值是这个区间的中位数，也就是堆只管理区间的一半（当然要另外开一个区域记录区间的实际大小）。
我们把每一个节点当做新的堆，如果序列是递增的，我们就把一个一个节点当做区间，并且不断压入栈，如果出现新入栈的节点的数值（也就是新的区间中位数，只有一个节点当然是节点的键值就是中位数了），那么我们就合并堆，直到合并到栈中的根的键值（中位数）是递增即可，同时，我们合并的时候，因为堆的信息只保留区间一半（包括中位数），也就是(len[k]+1)/2，如果出现新的堆和旧的堆合并，且(len[k]+1)/2+(len_new+1)/2>(len[k]+len_new+1)/2的时候（最多新的堆只会比要求大1），那么直接弹出堆的最大根，弹出后的堆根键值刚好就是符合条件的中位数。
参考：http://blog.csdn.net/iaccepted/article/details/6748038
http://m.blog.csdn.net/blog/u013595779/44004041
代码：
#include <iostream>
#include <functional>
#include <algorithm>
#define NullNode -1
#define MAX_N 2001 using namespace std; typedef int Position;
typedef struct _leftistheap
{
int value;
Position left, right;
int Npl;
}Left_Heap;
Position Merge1(Position, Position, Left_Heap *);
Position Merge2(Position, Position, Left_Heap *); static int len[MAX_N];
static int road[MAX_N];
Position stack[MAX_N];//中点栈组
Left_Heap Increase_Set[MAX_N]; long long Search(const int, Left_Heap *);
void Swap(Left_Heap *, Position); int main(void)//O(nlogn)处理3666
{
int n;
long long ans1;
while (~scanf("%d", &n))
{
memset(Increase_Set, -, sizeof(Increase_Set));
for (int i = ; i < n; i++)
{
scanf("%d", &road[i]);
Increase_Set[i].value = road[i];
Increase_Set[i].Npl = ;
}
ans1 = Search(n, Increase_Set);
printf("%lld\n", ans1);
}
return ;
} Position Merge1(Position H1, Position H2, Left_Heap *Node_Set)
{
if (H1 == NullNode)
return H2;
else if (H2 == NullNode)
return H1;
else if (Node_Set[H1].value >= Node_Set[H2].value)//注意符号！！！
return Merge2(H1, H2, Node_Set);
else
return Merge2(H2, H1, Node_Set);
} Position Merge2(Position H1, Position H2, Left_Heap *Node_Set)
{
if (Node_Set[H1].left == NullNode)
Node_Set[H1].left = H2;
else
{
Node_Set[H1].right = Merge1(Node_Set[H1].right, H2, Node_Set);
if (Node_Set[Node_Set[H1].left].Npl < Node_Set[Node_Set[H1].right].Npl)
Swap(Node_Set, H1);
Node_Set[H1].Npl = Node_Set[Node_Set[H1].right].Npl + ;//不能用pos2了，已经变了
}
return H1;
} void Swap(Left_Heap *Node_Set, Position x)
{
Node_Set[x].left ^= Node_Set[x].right;
Node_Set[x].right ^= Node_Set[x].left;
Node_Set[x].left ^= Node_Set[x].right;
} long long Search(const int n, Left_Heap *Node_Set)
{
memset(len, , sizeof(len));
int top = , sum_node_tmp, pos, k;
long long ans = ; for (int i = ; i < n; i++)
{
sum_node_tmp = ; pos = i;
while (top > && Node_Set[stack[top - ]].value > Node_Set[pos].value)
//左式堆只储存左半树的信息，也就是以中位数为最大的最大堆
{
pos = Merge1(stack[top - ], pos, Node_Set);//合并成一棵新的堆，现在新的堆的堆头就是新的区间中位数
if ((len[top - ] + ) / + (sum_node_tmp + ) / > (len[top - ] + sum_node_tmp + ) / )
//如果比保留长度大（而且只会大1，则弹出最大节点）
pos = Merge1(Node_Set[pos].left, Node_Set[pos].right, Node_Set);
sum_node_tmp += len[--top];
}
len[top] = sum_node_tmp;
stack[top++] = pos;
} for (int i = , j = ; i < top; i++)
{
k = Node_Set[stack[i]].value;
while (len[i]--)
ans += abs(road[j++] - k);
}
return ans;
}
这是0（nlogn）的算法，优化程度立竿见影