数据结构-堆

一、什么是堆

1.堆的定义：

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

堆中某个节点的值必须大于等于或者小于等于子节点的值

堆总是一棵完全二叉树。

根据结点是否大于等于或者小于等于子节点的值可以将堆分为两类：

1大顶堆：结点的值大于等于子节点的值

2小顶堆：结点的值小于等于子节点的值

常见的堆有二叉堆、斐波那契堆等。

2.堆的存储

堆在内存中通常是采用一个一维数组进行存储的，通过下面的步骤可以了解堆是如何存储的

2.1把堆中的结点按照从上到下从左到右的顺序进行编号

2.2把这些编号对应到一个数组的下标，然后把树的元素存储到对应的下标里

2.3通过上图可以总结出结点下标之间的规律

假设一个结点下标为i

该节点左子节点的下标为：2i+1

该结点右子节点的下标为：2i+2

二、堆的基本操作

堆有两个基本操作分别为上滤和下滤（也可称为 上浮和下沉），运用这两个操作基本能实现堆的所有的功能

下滤操作的实现

上图中，黄色方框中的结点满足堆的性质，只有根节点不满足，那我们要怎么操作才能把上面的树调整成堆呢

1.我们将破坏堆序性的结点（上图中红色结点）跟它的最大子节点进行比较，如果比最大子节点小就交换位置

1比最大子节点7小交换他俩位置

2.持续比较、交换、知道该结点大于它的子节点或者该结点变为叶子节点为止（这里的该结点为最初不满足堆序性的结点1）

1比最大子节点5小交换位置

此时上面的树满足的堆的性质，我们把这个过程称之为下滤

通过上面的操作可以分析出下滤操作的时间复杂度为O（logN）

疑问？为啥要和最大子节点进行比较呢

上滤操作的实现

此时假设最后一个元素8破坏了堆序性

1我们将破坏堆序性的结点（上图中红色结点）跟它的父节点进行比较，如果比父节点大就交换位置

8比6大交换位置

2继续和父节点比较，直到无法上移为止

8比7大交换位置

此时上面的树满足的堆的性质，我们把这个过程称之为上滤

上面这个操作主要用户插入新元素到堆中，时间复杂度也为O（logN）

三、如何构建一个堆

1自顶向下建堆法

操作步骤：从上到下从左到右依次插入结点，当不满足堆序性时进行上滤操作

依次从数组中插入3和4，此时发现不满足大顶堆的性质，进行上滤操作，交换3和4结点的位置

继续插入元素，直到数组元素插入完成

中间省略相同步骤，自行进行脑补

建堆完成，总过程时间复杂度为O(NlogN),

疑问？为什么时间复杂度时这样？

答：遍历数组获取插入元素时间复杂度是O(N)，然后插入结点上滤操作时间复杂度为O(lonN)所以总时间复杂度为O(NlogN)

2自下而上建堆法

先把数组中元素依次放入（从上到下从左到右）完全二叉树中，然后堆父节点进行下滤操作

先把下面的元素调整成堆，然后再对父节点进行下滤操作，具体操作是从倒数第二排开始对每个父节点进行下滤操作

父节点5比最大子节点8小，进行下滤操作

更具上面步骤从下到上从左到右进行操作，直到根结点操作完毕

这种建堆方法的时间复杂度为O(N)

四、优先队列

优先队列有两个操作：

1插入元素到队列

2弹出最小元素

因为是弹出最小元素，刚好小顶堆的根结点就是最小元素，所以把跟结点弹出

弹出后要将剩下的元素调整成堆

方法：将最后一个元素放到根节点，然后进行下滤操作

下滤操作

以此类推直到所有节点都弹出，此时相当于堆的删除操作时间复杂度为O(logN)

插入操作：上滤操作就是插入堆的操作时间复杂度为O(logN)

五、堆排序

通过上面的优先队列的内容已经可以联想到如何进行堆排序了，只要将优先队列的所有元素依次弹出就可以了

先弹出根元素1，然后最后一个元素12放到根结点，然后进行下滤操作，之后2就变为根结点了，然后再弹出2，如此反复，直到所有节点全弹出

上面的操作存在一个问题就是弹出元素后原来的堆空间不就浪费了吗？

为了解决这个问题，可以把排序的结果存放到堆空间的空缺单元里

完善过程

这里我们采用大根堆来做堆排序，至于为什么用大根堆，等到排序完就知道了

1、弹出根节点10，然后最后一个节点2上移到根节点，弹出的10存入的原来最后一个节点2的位置

2、2下滤来满足堆序性

3、弹出节点7，最后一个节点1上移到根节点位置，7存入原来1节点的位置

重复2，3步骤

从上面的最后结果可以看出从最开始的大根堆变为了小根堆，此时数组中的元素刚好是升序排序的，这就是为什么最开始用大根堆存储元素的原因，如果想用降序可以最开始使用小根堆时间复杂度为O(NlogN)

上述内容均参照哔哩哔哩工程部老周的视频总结出来的：

链接：【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆_哔哩哔哩_bilibili