本篇博客简介： 讲解堆和堆排序相关算法
堆和堆排序
- 堆
- 堆的概念
- 堆的性质
- 堆的表示形式
- 堆的增加
- 删除堆的最大值
- 堆排序
- 堆排序思路
- 时间复杂度为N的建堆方法
- 已知一个近乎有序的数组 使用最佳排序方法排序
堆
堆的概念
这里注意！！！ 这里说的堆和操作系统里面的堆没有半点关系！！！
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
上面这个就是官方的解释了
但是要是我们用通俗的话来说
就是这样子的
大堆 就是所有的父节点都大于等于子节点的堆
小堆 就是所有的子节点都小于等于父节点的堆
如图
堆的性质
-
堆总是一棵完全的二叉树
-
堆中某个节点的值总是不大于或者不小于其父节点的值
什么是完全二叉树呢
它要么是一颗满二叉树 要么它正在变满的路上
堆的表示形式
我们一般使用一个数组来从存储结构上表示一个堆 而堆在逻辑结构上表示一颗二叉树
具体的示例如下
假设我们现在有如下的一个数组
现在要将其转化为一颗完全二叉树
我们在上文说过一句话 堆要么是一颗满二叉树 要么在变成满二叉树的路上
所以说 我们只要按照满二叉树的形式构造一颗二叉树 到最后构造出来的一定是一颗完全二叉树
而满二叉树每一层的节点格式是确定的 所以说我们从第一层开始 依次拿一个数字 两个 数字 四个数字… 构造即可
从上面的构造中 我们能发现这样子的一个规律
我们现在假设 i 为数组的下标 那么根据完全二叉树的特征 我们可以得出以下结论
如果i对应的节点左孩子 右孩子 父亲节点存在的话
i对应节点的左孩子节点下标一定是2*i+1i对应节点的右孩子节点下标一定是2*i+2i对应节点的父节点下标一定是(i-1)/2
堆的增加
我们假设现在有一个空数组 我们要用这个数组构建出一个大堆
现在依次插入数字 10 8 6 那么形成的逻辑结构如下
目前二叉树是一个完全二叉树 并且符合大堆的性质
可是如果我们下一个数字插入 12 那么我们就破坏了这个大堆了
插入数字 12 之后就会出现子节点大于父节点的情况 这明显和我们上面讲的大堆的性质不符
此时为了让我们的大堆继续生效 我们就需要将出问题的节点向上调整
而又根据我们上面将的性质 一个节点通过公式 (i-1)/2 就能够找到它的父节点
之后就是与父节点比大小 如果子节点大就交换它们的位置
可是我们交换一次之后并不能保证这就是个大堆了 所以说向上调整要一直调整到根节点或者说比较不过父节点为止
删除堆的最大值
我们想要删除堆中的一个数据 还要不改变这个堆的结构 这个时候怎么办呢
我们这里给出一种很巧妙的解法
我们先将最前面的元素和最后面的元素交换位置
然后再删除掉堆最后面的元素
之后开始向下调整这个堆
如上图所示
如果说一个堆有 14 个元素 其中下标为7的为止的值被修改成了一个未知的值 我们应该如何修改使得该堆正常
其实思路很简单 它的值变化只有三种可能 变大 变小 不变
不变的情况我们不考虑 如果变大或者变小 其他位置的值是不发生改变的
我们只需要对于该位置执行两个操作
- 向上调整
- 向下调整
如果向上调整调用成功 则说明上面的树已经恢复正常了 而下面的树根本就没变 所以说这个堆整体就正常了 我们也不不需要向下调整了
如果我们向上调整之后 这个堆没有变化 那一定说明上面没问题 下面出问题了 此时调用向下调整即可
堆排序
我们C++中是实现了堆这种数据结构的 具体内容可以参考我的这篇博客
此外这篇博客中还详细讲解了 向上调整和向下调整的算法 优先级队列
堆排序的时间复杂度
进行堆插入的过程要调用向上调整函数
我们假设 堆中有N的元素 那么这个堆的逻辑二叉树结构就有LogN层高
所以说我们最多最多要比较LogN次 因为每一次插入的时间复杂度都是LogN
如果我们插入N个数 那么时间复杂度就是 N*LogN了
堆排序思路
如果说现在给我们一个无序的数组 要让我们对于这个数组从小到大排序
那么我们可以构建一个小堆作为中间的数据结构
方法如下
- 首先将数组中的数组遍历一遍 并且放入到优先级队列中
- 优先级队列的根节点一定是最小值 所以我们每次拿数据一定保证是比后面值要小的
- 我们从0下标开始填数据 每次下标加1并且填写根节点的值 直到堆中没有数据为止
时间复杂度为N的建堆方法
我们如果每次都是在最后插入数据 不停向上调整的话 建堆的时间复杂度是趋近于N*LogN的
但是在一定条件下 我们的建堆时间复杂度可以达到 N 需要达到的条件如下
- 我们要知道数组的大小
- 我们要知道所有需要插入的数字
建堆思路如下
- 我们从最后一层最后一个结点开始建堆 使用向下调整的算法
- 调整完最后一层之后我们继续从上一层的最后一个节点开始 插入数据 使用向下调整的算法
- 重复上面的步骤
下面是我的笔记分析
已知一个近乎有序的数组 使用最佳排序方法排序
我们现在已知一个几乎有序的数组 请选择一个合适的排序方法将其排序 并说明时间复杂度是多少
- 几乎有序的指的是 如果把数组排好序的话 每个元素移动的距离一定不超过K
解决这个问题我们的思路还是使用堆排序
我们假设K值为5
那么我们现在建立一个小堆 堆的大小为6 那么我们可以肯定的说 这个小堆的根节点就是这个数组的最小值
因为这六个数中肯定会有数组的最小值 而我们排序获取了这六个数的最小值 那么该值就一定是数组的最小值了
之后我们数组中的第二小值肯定在第2~7个数字中 我们只需要将数组的后一个元素插入小堆中即可找到
之后按照上面的方法 排一个插一个 排一个插一个
我们一共排了N个数字 每个数字最坏的情况要交换LogK次
所以说 最坏的时间复杂度为 NLogK 当K足够小的时候 时间复杂度可以近似看作NLogK
