1.堆的概念和特性

堆是将一组数据按照完全二叉树的存储顺序,将数据存储在一个一维数组中的结构。

堆分为两种:

  • 大顶堆:任意节点的值均大于等于它的左右孩子,并且最大的值位于堆顶,即根节点处。
  • 小顶堆:任意节点的值均小于等于它的左右孩子,并且最小的值位于堆顶,即根节点处。

如图:

image-20240405224417043

可能会有不同的叫法:有些地方也叫大根堆、小根堆,或者最大堆、最小堆都一个意思

问:堆就是优先队列吗?

  • 优先队列还是一种队列,能够实现优先功能的策略不一定只有堆,例如二项堆、平衡树、线段树、C++里会用二进制分组的vector来实现一个优先队列。
  • 堆是一个很大的概念 他并不一定是完全二叉树。我们之前用完全二叉树是因为这个很容易被数组储存,但是除了这种二叉堆之外,我们还有二项堆、斐波那契堆、这种堆就不属于二叉树。

但是java的PriorityQueue就是堆实现的,因此在java领域可以认为堆就是优先级队列,优先级队列就是堆,换做其他场景则不行。

2.堆的构造过程

这里介绍一个大堆的建立过程:

  1. 首先这里找到堆中最后一个节点:int i = (size - 2)/2 = 4,65大于其孩子,满足大堆性质,所以不用交换。

这里的size是堆中元素的数量,至于为什么是size-2/2的原因也是为了得到一个整数节点,因为不确定是左右节点,但是为了算出的结果为整数,因此可以直接算size-2

这里如果忘记,可以回顾二叉树中,数组表示的时候,父节点和左右节点的关系:

在二叉堆中(特别是当它被表示为数组时),给定一个节点的索引 i,其左子节点的索引是 2*i + 1,右子节点的索引是 2*i + 2

image-20240405225940421

  1. 然后i= i-1,然后用2和其孩子比较,2和204交换。交换之后204所在的子树满足大堆,如下左图。

image-20240405230329539

  1. 继续i=i-1,54和其孩子比较,54和92交换。此时92所在子树满足大堆,如下右图。

image-20240405230442532

  1. 继续,23和其孩子比较,23和204交换,交换完之后,23的子树却不满足了,所以还需调整它的子树。 如下两图所示。

image-20240405230506317

  1. 12和204交换,仍然出现不平衡的情况,以此类推,直到根节点也满足要求就完毕了。

image-20240405230520654

至此,一个大堆就建好了,但是左右节点的大小并不确定,还需要比较才行

3.堆的插入

插入一个元素的时候,我们已经知道,在一个根节点中并没有特别的规律,因此:

假如,插入300为例子:

我们先插入到最后的根节点31,之后通过不断调整顺序即可完成!

31<300,所以两者要交换,再向上发现300比65大,所以两者要交换。最后300比根元素204大,两者也交换。最后就得到了新的堆。

image-20240405230806525

4.堆的删除

堆本身比较特殊,一般对堆中的数据进行操作都是针对堆顶的元素,即每次都从堆中获得最大值或最小值,其他的不关心, 因此当删除堆顶的过程一般是:

先将堆中最后一个元素(假如为A)和堆顶元素进行替换,然后删除堆中最后一个元素。之后再从根开始逐步与左右比较,谁更大谁上位。然后A再继续与子树比较,如果有更大的继续交换,直到自己所在的子树也满足大顶堆。

image-20240405231325825

更新后的堆

image-20240405231408182

简单理解过程就是,因为堆顶必须留元素,所以想要删除必须要找一个临时的代替

总结

问:堆的增加和删除并不简单,为什么会说堆的效率高呢?

堆元素的数量是有限制的,一般不用将所有的元素都放到堆里。后面题目中可以看到,在序列中找K大,则堆的大小就是K。如果K个链表合并,那么堆就是K。

下面是两个常用的口诀:

  • 查找:找大用小,大的进;找小用大,小的进。
  • 排序:升序用小,降序用大。

解释就是:是找K大,则用小堆,后续数据只有比根元素更大时才允许进入堆。如果是找K小,则对应反过来。后面我们结合例子分析为什么。