优先队列
左偏树
左偏树和最小堆非常类似，二者的构建时间均为$O(n)$，可以以$O(\log_2n)$的时间复杂度弹出最小元，以$O(\log_2n)$时间复杂度插入新的元素。但是左偏树有一个能力是最小堆无法做到的，大小为n和m的两个左偏树合并，只需要$O(\log_2nm)$，而最小堆使用启发式合并的思路也只能达到$O(\min(n,m)\log_2(n+m))$。
左偏树的实现非常简单。每个左偏树结点拥有四个属性，左孩子、右孩子、关键字、距离。前三个属性和一般平衡树无异，第四个属性是什么呢？我们认为空结点的距离为-1，认为一个非空结点的距离为左右结点的距离中最小值加1。由于在堆中左右子结点没有大小关系，因此我们始终将左结点设为子结点中距离较大者，此时可以直接认为结点的距离为右子结点的距离加1。
命题1：只有n个结点的左偏树，其距离不可能超过$\log_2n$。
我们记f(x)表示拥有x个结点的左偏数根节点距离的最大值。当n=1时，命题显然成立。假设当n<k时，命题始终成立。那么当n=k时，我们设左子树下有x个结点，右子树下的结点数为$k-1-x$。
\[f(k)=1+\min(f(x),f(k-1-x))\leq 1+f(\lfloor \frac{k-1}{2} \rfloor)\leq 1+\log_2\frac{k-1}{2}\leq \log_2k\]下面说一下左偏树的核心操作，合并两个左偏树。假设两个左偏树分别为a、b，不妨认为a的关键字不大于b的关键字。我们将b与a的右结点合并，之后维护a，保证a满足左偏树的特性（右子结点的距离不超过左子结点，同时a的距离等于右结点的距离加1）。
merge(a, b){
if(a.key > b.key)
{
swap(a, b);
}
merge(a.right, b);
if(a.right.distance > a.left.distance)
{
swap(a.left, a.right);
}
a.distance = a.right.distance + 1;
return a;
}
由于每次递归，a、b中一个结点距离保持不变，一个结点的距离减少1，由于两个大小为n、m的左偏树的距离和不超过$O(\log_2n+\log_2m)$，因此可以证明函数调用次数不会超过$O(\log_2n+\log_2m)$，时间复杂度也是$O(\log_2nm)$。
左偏树的删除最小元，我们只需要将根节点的左右子树合并即可。而插入新的元素，等价于创建一个只有单结点的左偏树，之后与原树合并即可。二者的时间复杂度均为$O(\log_2n)$。
建图和最小堆一样，有线性的做法。首先将所有只有一个结点的左偏树放入到队列中。之后不断从队列头部弹出两个左偏树合并后加入到队列末尾。可以推出时间复杂度为$\sum_{i=1}^{\log_2n}\frac{n}{2^i}(2\log_2i+1)$。这个求和式和建堆的一致，均为$O(n)$。