数据结构总结-堆
堆结构是一类很重要的数据结构,特别是在实现优先队列方面。
堆结构实际上都是树(或森林),不过按节点的存储方式又可以分为两种
- 顺序存储
这种情况下,必须保持是完全树。 (在插入,删除后及时调整)
可以通过下标运算找到父节点,字节点。 - 链接存储
如果是二叉树,一般就用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) |