各种堆——二叉堆,d堆,左式堆,斜堆,二项队列,斐波那契堆

二叉堆

二叉堆就是一个完全二叉树。几乎在所有需要用到优先队列的时候,使用它就完事了。

D-堆

D堆就是一个完全d叉树。所以,d堆会比二叉堆浅的多。

左式堆

Clark Allan Crane,1972年发明。叫这个名字地原因就是这个树左边比右边高。

零路径长:从节点X到一个没有两个子节点的(有一个子节点或没有子节点)节点的最短距离

左式堆首先是一个二叉查找树。附加一个条件

要求任一节点的左子节点零路径长大于等于右子节点的零路径长

左式堆的合并过程
第一步,符合堆的原则进行合并。
各种堆——二叉堆,d堆,左式堆,斜堆,二项队列,斐波那契堆
第二步,对于不符合的左式堆要求的节点,请调换左右节点。
各种堆——二叉堆,d堆,左式堆,斜堆,二项队列,斐波那契堆

斜堆

斜堆是左式堆的自调节形式。其和左式堆的关系类似与伸展树和AVL树之间的关系。

二项队列

斐波那契堆