堆排序
堆排序是一种原地的、时间复杂度为 O(nlogn) 的排序算法。
什么是堆
- 堆是一个完全二叉树(除了最后一层,其他层的节点个数都是满的,最后一层的节点都靠左排列);
- 堆中每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值
分类
堆分为大顶堆和小顶堆。
大顶堆是所有父节点都大于其子节点大
小顶堆所有父节点都小于其子节点
1 是大顶堆
3 是小顶堆
如何实现一个堆
完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针,单纯地通过数组的下标,就可以找到一个节点的左右子节点和父节点。
堆化(插入一个数,调整,维持堆的特性)非常简单,就是顺着节点所在的路径,向上或者向下,对比,然后交换。
如何基于堆实现排序
我们可以把堆排序的过程大致分解成三大步骤,建堆、堆化、堆排序。
建堆
首先将数组原地建成一个堆。所谓“原地”就是,不借助另一个数组,就在原数组上操作。就是按照数组的顺序,放到对应数的位置上, 不需要进行额外操作。
堆化
以大顶堆为例,一般按照从下往上、从右向左进行堆化操作,先找到最后一个端节点(非子节点),将其与子节点进行对比,比端节点大的与端节点进行交换,确保端节点以下的节点都比端节点小,以此类推,层层向上堆化,确保顶级元素最大。
堆排序
调整堆,调整过程需要保证堆序性质:在一个二叉堆中任意父节点大于其子节点。
1、堆排序,取出位于堆顶的第一个数据(最大堆则为最大数,最小堆则为最小数),与最后一个元素进行交换,对剩余元素进行堆化
2、继续按照步骤1进行,取出堆最低层节点与根节点互换,再进行堆化。
3、最后输出排序好的数组。
评价
评价算法好坏
堆排序是非稳定的排序算法
分类:排序算法
数据结构:数组
最优时间复杂度:O(n*log(n)),当keys 的值都不一样;O(n),当keys 的值都一样
最坏时间复杂度:O(n*log(n))
平均时间复杂度:O(n*log(n))
最坏空间复杂度:辅助O(1)
时间复杂度
代码实现
// 调整堆 调整为大顶堆
function heapAjust(data, i, len) {
let child = 2 * i + 1; // 左子节点
while(child <= len) {
// 如果右子节点存在 且大于左节点值,child指向右节点
if (child + 1 <= len && data[child] < data[child + 1]) {
child = child + 1;
}
// 入股当前节点值小于子节点 互换
if (data[child] > data[i]) {
[data[i], data[child]] = [data[child], data[i]];
i = child;
child = 2 * i + 1;
} else {
break;
}
}
}
// 堆排序
function heapSort(A) {
// 建堆 从后往前 从右向左 构建大顶堆
for(let i = Math.floor((A.length - 2) / 2); i >= 0; i--) {
heapAjust(A, i, A.length);
}
// 堆排序 最下面元素与堆顶元素交换
for(let j = A.length - 1; j > 0; j--) {
[A[j], A[0]] = [A[0], A[j]];
// 大顶推排序 从顶向下调整堆 移到尾部的不参与排序 最后效果从小到大排序
heapAjust(A, 0, j - 1);
}
return A;
}
heapSort([10,3,22,3,233,34,55,6])