for (let i = 0, length = arr.length; i < length; i++) {
//将堆(完全二叉树)的根结点拿走,放入result数组,此时result是已排序好的。
swap(0, length-result.length);
//然后下沉,重排树,让根节点是最小的。注意【数组范围】是length-result.length
sink(arr, 0, length - result.length);
function buildMinHeap(arr) {
let currentIndex;//当前要处理的下沉结点对应的数组索引
//请注意,currentIndex为什么是从 Math.floor((length - 2) / 2) 开始?
//这会让算法的循环次数由N次变为logN,这正是堆排序更高效的关键所在。
for (currentIndex = Math.floor((length - 2) / 2); currentIndex >= 0; currentIndex--) {
console.log("正在处理的下沉结点索引为:"+currentIndex);
sink(arr, currentIndex, length);
* @param currentIndex 要处理的结点的索引,该结点有子结点
function sink(arr, currentIndex, length) {
let minIndex=currentIndex;//较小值的索引,默认为currentIndex
let leftChildIndex = 2*currentIndex+1;//完全二叉树 左子结点索引
let rightChildIndex = 2*currentIndex+2;//完全二叉树 右子结点索引
if(leftChildIndex < length && arr[leftChildIndex] < arr[minIndex])
minIndex = leftChildIndex;
if (rightChildIndex < length && arr[rightChildIndex] < arr[minIndex])
minIndex = rightChildIndex;
if(minIndex!=currentIndex){
swap(minIndex,currentIndex);
sink(arr,minIndex,length);
})([1, 5, 4, 2, 9, 7, 8]);//>> [1, 2, 4, 5, 7, 8, 9]