堆结构是一类很重要的数据结构,特别是在实现优先队列方面。
堆结构实际上都是树(或森林),不过按节点的存储方式又可以分为两种

  1. 顺序存储
    这种情况下,必须保持是完全树。 (在插入,删除后及时调整)
    可以通过下标运算找到父节点,字节点。
  2. 链接存储
    如果是二叉树,一般就用LeftChild,RightChild 两个指针。
    否则一般用环链表表示一个 节点的子女。

下面的表格在blog 中显得很拥挤,建议在这里查看.


数据结构 存储方式 定义与性质 支持的操作 及 复杂度(分摊)
最大堆 顺序存储 完全二叉树,最大树 插入
O(log n)
删除最大元素 O(log n)
最小最大堆 顺序存储 完全二叉树,树的各层交替为最小层和最大层 插入
O(log n)
删除最大元素 O(log n)
删除最小元素 O(log n)
双堆 顺序存储 完全二叉树
或者为空,或者同时满足:
1.根结点不含元素
2.左子树是最小堆
3.右子树为最大堆
4.若右子树不为空,设i 为左子树中的任意结点,
j为右子树的对应结点.
若j不存在,则令j为右子树中对应i的父结点的结点。
必有结点i的key 小于 结点j的key值
插入
O(log n)
删除最大元素 O(log n)
删除最小元素 O(log n)
左偏树
(最小/最大)
链接存储 1.是左偏树
每一个内部结点x 有
shortest(LeftChild(x))
>=shortes(RightChild(x))
2.是最小/最大树
插入
O(log n)
删除最小/最大元素 O(log n)
合并 O(log n)
二项式堆
(最小/最大)
链接存储 最小/最大二项式树的集合.
度为k的二项式树(记作Bk)定义为:
若k=0,该树只有1个结点.
若k>0,该树的根的度为k,其子树为B,B1,…..,Bk-1
插入 O(1)
删除最小/最大元素 O(log n)
合并 O(1)
斐波纳契堆
(最小/最大)
链接存储 最小/最大树的集合.
二项式堆是斐波纳契堆的特殊情况.
使用双环链表,并在结点中加入parent和childcut.
关键是瀑布修剪
插入 O(1)
删除最小/最大元素 O(log n)
合并 O(1)
减少指定结点key值
O(1)
删除指定结点元素
O(log n)