【堆】堆的数据结构，以及堆排序的优缺点、时间复杂度分析_最小堆的时间复杂度

本来想写堆以及优先队列的，现在就只简单写写堆吧，先不写别的了，先把堆搞明白。

堆是什么

堆是一个 完全二叉树，每一个节点的值都必须 大于等于 或者 小于等于 其孩子节点的值。

堆的特点

插入 的时间复杂度：O(lgn)
删除 的时间复杂度：O(lgn)
获取最大值/最小值的 时间复杂度：O(1)

最大堆/最小堆

最大堆：每一个节点的值都必须 大于等于 其孩子节点的值。
最小堆：每一个节点的值都必须 小于等于 其孩子节点的值。

构建最大堆

构建最大堆的步骤分为一下几步：

1. 把要插入的元素插入到堆中
2. 和父节点做比较
   2.1 如果比父节点大，则和父节点交换值，继续重复第二步
   2.2 如果比父节点小，则结束插入

现有一个数组 [5, 2, 9, 4, 6]，将其构建成最大堆，构建过程如图所示

最大堆删除元素（删除堆顶元素）

总体分为两个操作，删除堆顶元素 和 把堆变换成最大堆

删除元素的详细步骤如下：

1. 删除堆顶元素，取堆的最后一个元素放到堆顶
2. 判断子节点是否大于当前节点值
   2.1 如果大于，选择两个字节点中较大的与当前节点交换，然后用交换的节点继续重复步骤2
   2.2 如果不大于，则删除结束，退出

因为我们构建的是最大堆，所以向外取元素时，只能取堆顶的元素。

堆排序

堆排序的核心思想，就是构建最大堆或最小堆，详细步骤如下：

1. 构建最大堆
2. 把堆顶元素和最后一个未排序元素进行交换
3. 重复1和2，直到最后一个元素位置

以数组 [1, 2, 9, 6, 4] 为例，进行堆排序

1. 把所有数据加入到堆中
   

2. 未排序元素构建最大堆，然后把堆顶元素和未排序的最后一个元素交换
   构建最大堆
   
   堆顶元素和未排序的最后一个元素交换
   

3. 排序第二个元素，重复步骤，未排序元素构建最大堆，然后把堆顶元素和未排序的最后一个元素交换
   构建最大堆
   
   堆顶元素和未排序的最后一个元素交换
   

4. 排序第三个元素，重复步骤，未排序元素构建最大堆，然后把堆顶元素和未排序的最后一个元素交换
   构建最大堆
   
   堆顶元素和未排序的最后一个元素交换
   

5. 排序第四个元素，重复步骤，未排序元素构建最大堆，然后把堆顶元素和未排序的最后一个元素交换
   构建最大堆
   
   堆顶元素和未排序的最后一个元素交换
   

6. 剩下最后一个元素，无需排序，堆排序结束
   

堆排序优点缺点（特点）

没有绝对的优缺点，想了想，只能叫堆排序的特点

堆排序的时间复杂度是O(nlgn)，堆排序的时间复杂度不是O(n2)，因为堆采用了额外的空间，来降低了时间复杂度。

不过，堆排序有一个明显的问题，不管数组是否有序或者无序，都要从头到尾进行一遍排序，就好像是没有优化过的冒泡排序一样，从头冒到尾。

也因为这个问题，使得在数据量较少时，堆排序的时间复杂度的常数比较高，进而导致排序时间较长。

（一般来讲，时间复杂度是省略了常数k之后，因为在n足够大之后，k对n的影响较小，但是在n较小的时候，k的影响还是比较大的）