本来想写堆以及优先队列的,现在就只简单写写堆吧,先不写别的了,先把堆搞明白。
堆是什么
堆是一个 完全二叉树
,每一个节点的值都必须 大于等于
或者 小于等于
其孩子节点的值。
堆的特点
插入
的时间复杂度:O(lgn)
删除
的时间复杂度:O(lgn)
获取最大值/最小值的
时间复杂度:O(1)
最大堆/最小堆
最大堆:每一个节点的值都必须 大于等于
其孩子节点的值。
最小堆:每一个节点的值都必须 小于等于
其孩子节点的值。
构建最大堆
构建最大堆的步骤分为一下几步:
- 把要插入的元素插入到堆中
- 和父节点做比较
2.1 如果比父节点大,则和父节点交换值,继续重复第二步
2.2 如果比父节点小,则结束插入
现有一个数组 [5, 2, 9, 4, 6]
,将其构建成最大堆,构建过程如图所示
最大堆删除元素(删除堆顶元素)
删除元素的详细步骤如下:
因为我们构建的是最大堆,所以向外取元素时,只能取堆顶的元素。
堆排序>堆排序
堆排序>堆排序的核心思想,就是构建最大堆或最小堆,详细步骤如下:
以数组 [1, 2, 9, 6, 4]
为例,进行堆排序>堆排序
-
把所有数据加入到堆中
-
排序第二个元素,重复步骤,未排序元素构建最大堆,然后把堆顶元素和未排序的最后一个元素交换
构建最大堆
堆顶元素和未排序的最后一个元素交换
-
排序第三个元素,重复步骤,未排序元素构建最大堆,然后把堆顶元素和未排序的最后一个元素交换
构建最大堆
堆顶元素和未排序的最后一个元素交换
-
排序第四个元素,重复步骤,未排序元素构建最大堆,然后把堆顶元素和未排序的最后一个元素交换
构建最大堆
堆顶元素和未排序的最后一个元素交换
堆排序>堆排序优点缺点(特点)
堆排序>堆排序的时间复杂度是O(nlgn),堆排序>堆排序的时间复杂度不是O(n2),因为堆采用了额外的空间,来降低了时间复杂度。
不过,堆排序>堆排序有一个明显的问题,不管数组是否有序或者无序,都要从头到尾进行一遍排序,就好像是没有优化过的冒泡排序一样,从头冒到尾。
也因为这个问题,使得在数据量较少时,堆排序>堆排序的时间复杂度的常数比较高,进而倒是排序时间较长。
(一般来讲,时间复杂度是省略了常数k之后,因为在n足够大之后,k对n的影响较小,但是在n较小的时候,k的影响还是比较大的)