堆排序
定义堆是一棵完全二叉树。分为大顶堆和小顶堆
大顶推：所有节点都大于等于它的两个子节点
小顶堆：所有节点都小于等于它的两个子节点
伪代码
推排序步骤，以升序排列为例，用大顶堆。（降序排列，用小顶堆）
[*]构建大顶推
[*]把堆顶元素和堆尾元素交换，此时堆尾元素是最大的，堆的大小减一
[*]堆顶元素下沉到指定位置
[*]重复2-3步，直到堆的大小为1
关键在于如何构建一个大顶堆（对节点进行下沉）:
从最后一个非叶子节点开始；
逐个检查每个节点，如果一个节点的值小于其子节点的值，我们就将它与较大的子节点交换位置；
交换后，这个交换后的节点可能导致不满足堆的特性，因此还需要继续下沉（Heapify)
举个例子
需要注意的是：对于一个完全二叉树
它的最后一个非叶节点下标是 Math.floor(len/2) - 1,len是二叉树的节点个数
下标为i的节点，它的左子节点是2*i+1, 右子节点是2*i+2
比如说对于
最后一个非叶子节点下标是Math.floor(len/2) - 1=2, 也就是说最后一个非叶子节点是7, 构建最大堆的过程如下：
时间复杂度
O(nlogn)
实现
function heapSort(arr) {
// 构建最大堆
let n = arr.length;
for(let i = Math.floor(n/2 - 1); i>=0;i--) {
heapify(arr, n, i) // 把下标为i的节点放到合适的位置上
}
while(n>1) {
// 交换堆顶元素和堆尾元素
, arr] = , arr]
// 堆的个数减一
n--
// 把堆顶元素放到合适的位置
heapify(arr, n, 0)
}
}
function heapify(arr, n, i) {
let largestIndex = i
let leftIndex = 2 * i + 1
let rightIndex = 2 * i + 2
if(leftIndex < n && arr > arr) {
largestIndex = leftIndex
}
if(rightIndex < n && arr > arr) {
largestIndex = rightIndex
}
if(largestIndex!==i) {
, arr] = , arr]
heapify(arr, n, largestIndex)
}
}
来源:https://www.cnblogs.com/duanlvxin/p/18395230
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！
页:
[1]