最大堆与最小堆

  • 更新时间: 2017-09-26
  • 来源: 原创或网络
  • 浏览数: 57次
  • 字数: 3827
  • 发表评论
最小堆,是一种经过排序的完全二叉树,其中任一非终端节点的数据值均不大于其左子节点和右子节点的值。

1 介绍

最大堆最小堆二叉堆的两种形式。

  1. 最大堆:根结点的键值是所有堆结点键值中最大者的堆。
  2. 最小堆:根结点的键值是所有堆结点键值中最小者的堆。

而最大-最小堆集结了最大堆最小堆的优点,这也是其名字的由来。 最大-最小堆是最大层和最小层交替出现的二叉树,即最大层结点的儿子属于最小层,最小层结点的儿子属于最大层。 以最大(小)层结n点为根结点的子树保有最大(小)堆性质:根结点的键值为该子树结点键值中最大(小)项。

2 主要操作

不失一般性,只讨论根结点为最小层的情况。

插入

只需要将节点插在二叉树的最后一个叶子结点位置,然后比较它对它父亲节点的大小,如果大则停止;如果小则交换位置,然后对父亲节点递归该过程直至根节点。复杂度为O(log(n))。

一般来说,插入的位置可以不是最后一个叶子节点,可以作为任意中间节点的孩子节点插入,将这个叶子节点变为中间节点后,按上文所说的方法调整节点顺序以保证维持堆特性不变。

删除

要从堆中删除一个节点,用最后一个节点替换掉根节点,然后调整节点顺序以维持堆特性。

最小堆是一棵完全二叉树,非叶子结点的值不大于左孩子和右孩子的值。本文以图解的方式,说明最小堆的构建、插入、删除的过程。搞懂最小堆的相应知识后,最大堆与此类似。

3 最小堆示例

最大堆与最小堆,by 5lulu.com



标签: 最小堆

我来评分 :6
0

转载注明:转自5lulu技术库

本站遵循:署名-非商业性使用-禁止演绎 3.0 共享协议