配对堆是一种实现简单、均摊复杂度优越的堆数据结构,由迈克尔·弗雷德曼、罗伯特·塞奇威克、丹尼尔·斯莱托、罗伯特·塔扬于1986年发明。
配对堆是一种多叉树,并且可以被认为是一种简化的斐波那契堆。对于实现例如普林姆算法等算法,配对堆是一个更优的选择,且支持以下操作:
伸展树是一种能够自我平衡的二叉查找树,它能在均摊
O
{\displaystyle O}
的时间内完成基于伸展操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特和罗伯特·塔扬在1985年发明的。
伸展树是一种能够自我平衡的二叉查找树,它能在均摊
O
{\displaystyle O}
的时间内完成基于伸展操作的插入、查找、修改和删除操作。它是由丹尼尔·斯立特和罗伯特·塔扬在1985年发明的。