各种堆——二叉堆,d堆,左式堆,斜堆,二项队列,斐波那契堆
二叉堆
二叉堆就是一个完全二叉树。几乎在所有需要用到优先队列的时候,使用它就完事了。
D-堆
D堆就是一个完全d叉树。所以,d堆会比二叉堆浅的多。
左式堆
Clark Allan Crane,1972年发明。叫这个名字地原因就是这个树左边比右边高。
零路径长:从节点X到一个没有两个子节点的(有一个子节点或没有子节点)节点的最短距离
左式堆首先是一个二叉查找树。附加一个条件
要求任一节点的左子节点零路径长大于等于右子节点的零路径长
左式堆的合并过程
第一步,符合堆的原则进行合并。
第二步,对于不符合的左式堆要求的节点,请调换左右节点。
斜堆
斜堆是左式堆的自调节形式。其和左式堆的关系类似与伸展树和AVL树之间的关系。