关于javascript:数据结构与算法堆排序

这里以最大堆为例，最大堆满足父节点的值既大于左子节点，又大于右子节点。所对于一个最大堆而言，根节点保留着堆中最大的值。理论利用中，堆数据保留在一个数组中，且因为堆能够看成是一棵满二叉树，数组中的元素从上到下，从左到右一次填充二叉树（如下图），因而树中的父子节点在数组中的索引领有固定的关系：

堆排序的基本思路是首先将待排序数组构建成一个最大堆，将堆顶的元素与堆的最初一个元素替换地位，同时将堆的尺寸减 1（行将最初一个地位的元素移除堆），调整残余元素，使之放弃堆的构造，而后反复下面的过程，直到堆中只有一个元素。

具体实现如下：

/**
 * 以最大堆为例
 */
// 获取子节点的索引
const left = index => 2 * index + 1;
const right = index => 2 * (index + 1);
// 替换数组中的两个元素
const swap = (arr, i, j) => {if (i === j) return;
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
};

// 对数组中的某个元素进行下沉操作
// 即如果以后元素小于某个子元素，则与该子元素替换地位，而后对子元素执行递归操作
function heapify(i, array, heapSize) {const l = left(i);
    const r = right(i);
    let largest = i;
    // 如果左子节点大于以后节点
    if (l < heapSize && array[l] > array[i]) {largest = l;}
    // 如果右子节点大于较大的值
    if (r < heapSize && array[r] > array[largest]) {largest = r;}
    if (largest !== i) {swap(array, i, largest);
        heapify(largest, array, heapSize);
    }
}

// 构建最大堆
function buildHeap(array) {
    // 从最初一个有子节点的元素开始，即最初一个元素的父节点的索引
    const start = Math.floor((array.length - 2) / 2);
    for (let i = start; i >= 0; i--) {heapify(i, array, array.length);
    }
}

// 堆排序
function heapSort(array) {buildHeap(array);
    for (let i = array.length - 1; i > 0; i--) {swap(array, 0, i);
        heapify(0, array, i);
    }
}

上面是测试代码及最终的运行后果：

const count = 20;
const arr = [];
for (let i = 0; i < count; i++) {arr.push(Math.floor(Math.random() * 100));
}
console.log('before sort:', arr);
heapSort(arr);
console.log('after sort', arr);