堆排序（二、生成一个最大堆）

我们上一篇文章，对堆进行了处理，shift up、shift down等操作。

这篇文章来介绍一下如何给定一个数组，生成一个最大堆？

下图是一个随机的数组，蓝色的部分表示的是叶子结点。

思考：

• 将叶子节点的最后一个（值：62；索引：10）与它的父节点（index/2）进行比较。
• 做shift down操作。
• 这样从索引值5开始，到它的子节点之后，就满足了最大堆的形式。
• 此时我们的数组就变成了如下图：

思考：

• 如果索引10，以及他的父节点索引5，已经满足最大堆条件。
• 那它的索引9和8的父节点是不是也可以进行shift down的操作，来达到最大堆的要求？
• 答案是肯定的。
• 那我们的索引6和7的父节点呢？索引4和5的父节点呢？索引2和3的父节点呢？
• 我们发现，经过不断的shift down的操作，我们最终将一个随机的数组转换成了最大堆。
• 但是要注意：当我们算索引为4和5的父节点的时候，索引2到子节点索引4和5为最大堆之后，4这个节点的子节点索引8和9还要继续进行运算，或者是5的子节点10还要进行运算，不会出现4和5都需要shift down操作的情况。

看下图对比上图，方便仔细思考：

// 最大堆排序
// 给定一个数组，将这个数组形成堆的形式
// Heapify
let arr = ["", 15, 17, 19, 13, 22, 16, 28, 30, 41, 62]
let arrLength = arr.length
function swap(arr, leftIndex, rightIndex) {    
    [arr[leftIndex], arr[rightIndex]] = [arr[rightIndex], arr[leftIndex]]
}
function shiftDown(arr, k) {    
    while (k * 2 <= arr.length) {        
    let j = k * 2        
    if (j + 1 <= arr.length && arr[j + 1] > arr[j]) {             
        j+=1;        
    }        
    if (!arr[j] || arr[k] > arr[j]) {            
        break;        
    }        
        swap(arr, k, j)        
        k = j;    
    }    
    return arr;
}
function heapify(arr, arrLength) {    
    for (let i = parseInt((arrLength - 1) / 2); i >= 1; i--) {        
        shiftDown(arr, i)    
    }    
    return arr;
}
console.log(heapify(arr, arrLength))

最大堆排序

虽然上一篇文章已经介绍过如何排序，但是避免大家再去翻找，我就再来实现一下。

以下是实现，大概的思路在备注中，详细的思路不写在这里了，想看还是去上一篇文章里面找吧。感谢大家支持！！！

因为生成最大堆的时候不需要对数组进行splice，可是在排序的时候还需要，而一个shiftDownd函数满足两种情况，并且返回值不同，所以要进行封装判断。

// 最大堆排序
// 给定一个数组，将这个数组形成堆的形式
// Heapify
let arr = ["", 15, 17, 19, 13, 22, 16, 28, 30, 41, 62]
let arrLength = arr.length
// 排序，交换位置
function swap(arr, leftIndex, rightIndex) {    
	[arr[leftIndex], arr[rightIndex]] = [arr[rightIndex], arr[leftIndex]]
}
// 将check封装，arr数组在排序时才需要切割
function check(arr){    
	let arraySplice = arr.splice(arr.length-1, 1)    
    let arrSpliceMax = arr.splice(1, 1)    
    arr.splice(1, 0, arraySplice[0])    
    return arrSpliceMax;
}
function shiftDown(arr, k, flag) {    
	let arraySplice = [];    
    if(flag){        
    	arraySplice.push(...check(arr))    
    }    
    while (k * 2 <= arr.length) {        
    	let j = k * 2        
        if (j + 1 <= arr.length && arr[j + 1] > arr[j]) {            
        	j += 1;        
        }        
        if (!arr[j] || arr[k] > arr[j]) {            
        	break;        
        }        
        swap(arr, k, j)        
        k = j;    
    }    
    let arrMax = !flag? arr : arraySplice    
    return arrMax
}
// 取最后一个子叶节点的父节点索引值
// 进行shift down
function heapify(arr, arrLength) {    
	for (let i = parseInt((arrLength - 1) / 2); i >= 1; i--) {
    	shiftDown(arr, i, false)    
    }    
    return arr;
}
let arrayHeap = heapify(arr, arrLength);
console.log(arrayHeap)
// 排序
// 思路是取出最大值，然后将最后值放在第一位（index=1的位置）
// 继续
shift downfunction heapSort(arr) {
	let array = []    
   	for (let i = 1; i < arr.length; i++) {
    	array.push(...shiftDown(arr, 1, true))
    }
    arr.splice(arr[0], 1)    
    array = [...array, ...arr]    
    return array
}
console.log(heapSort(arrayHeap))