【算法与数据结构专场】二叉堆是什么鬼?

二叉堆是一种应用很广的数据结构,今天,我们就来简单讲讲二叉堆。
往期回顾:
算法与数据结构专场】BitMap算法基本操作代码实现
【算法与数据结构专场】BitMap算法介绍

什么是二叉堆?

二叉堆是一种特殊的堆。具有如下的特性:

具有完全二叉树的特性。

堆中的任何一个父节点的值都大于等于它左右孩子节点的值,或者都小于等于它左右孩子节点的值。

根据第二条特性,我们又可以把二叉堆分成两类:
1、最大堆:父节点的值大于等于左右孩子节点的值。

【算法与数据结构专场】二叉堆是什么鬼?

2、最小堆:父节点的值小于等于左右孩子节点的值。

【算法与数据结构专场】二叉堆是什么鬼?

我们把二叉堆的根节点称之为堆顶。根据二叉堆的特性,堆顶要嘛是整个堆中的最大元素,要嘛是最小元素

今天,我们主要来讲讲二叉堆的三个主要操作:

插入一个节点。

删除一个节点。

构建一个二叉堆。

不过这里需要注意的是,在二叉堆这种结构中,对于删除一个节点,我们一般删的是根节点
下面我们以最小堆为例子,来讲讲这些操作。

插入一个节点。

刚才我们说二叉堆具有完全二叉树的特性,因此,我们在插入一个节点的时候,应该先保证节点插入后,它仍然是一颗完全二叉树,然后再来进行调整,使它满足二叉堆的另一个特性。
所以,在插入的时候,我们把新节点插到完全二叉树的最后一个位置。例如:

【算法与数据结构专场】二叉堆是什么鬼?


插入0。

【算法与数据结构专场】二叉堆是什么鬼?

之后我们再来进行调整,调整的原则是:让新插入的节点与它的父节点进行比较,如果新节点小于父节点,则让新节点上浮,即和父节点交换位置。
上浮之后继续和它的父节点进行比较,直到父节点的值小于或等于该节点,才停止上浮,即插入结束。例如:
0比5小,上浮。

【算法与数据结构专场】二叉堆是什么鬼?


0比2小于,上浮。

【算法与数据结构专场】二叉堆是什么鬼?

0比1小,上浮。

【算法与数据结构专场】二叉堆是什么鬼?


已经到达堆顶了,插入结束。

【算法与数据结构专场】二叉堆是什么鬼?

删除节点。

前面说了,删除节点一般删除的是根节点。
和插入一样,由于二叉堆具有完全二叉树的特性,因为删除时候,首先我们是要马上恢复它具有完全二叉树的特性,所以我们是采取这样的策略:把根节点删除之后,用二叉堆的最后一个元素顶替上来,然后在进行调整恢复。例如:

【算法与数据结构专场】二叉堆是什么鬼?

把0删除了之后,5替换上来。

【算法与数据结构专场】二叉堆是什么鬼?

之后再来调整,调整的规则和插入差不多类似,采取下沉的策略:让5和左右孩子节点相比较,如果左右节点有小于5的,则让那个较小的孩子代替5的位置,然后5下沉。
下沉之后,5继续和左右孩子相比,直到左右孩子都大于或等于5才结束。
如:5比1,3都大,1代替5的位置

【算法与数据结构专场】二叉堆是什么鬼?

5比4,2都大,2代替5的位置。

【算法与数据结构专场】二叉堆是什么鬼?

5已经不在具有左右孩子了,删除结束。

【算法与数据结构专场】二叉堆是什么鬼?

构建二叉堆

所谓构建,就是给你一个有n个节点的无序的完全二叉树,然后把它构建成二叉堆。
刚才我们在删除一个节点的时候,把最后一个元素补到根元素的位置上去,然后再让这个元素依次下沉,实际上,在这个元素还没有下沉之前,它就可以看作是一颗无序的完全二叉树了
也就是说,要把一个无序的完全二叉树调整为二叉堆,我们可以让所有非叶子节点依次下沉。不过下沉的顺序不是从根节点开始下沉(想一下相必你就 知道不能从根节点开始下沉),而是从下面的非叶子节点下称,在依次往上。举个例子:
对于这样一颗无序的完全二叉树

【算法与数据结构专场】二叉堆是什么鬼?


8进行下沉。

【算法与数据结构专场】二叉堆是什么鬼?

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zywxpx.html