堆排序-最大堆的js实现 #1
Description
彩色版本
文字版本
// 堆排序算法
// 1. 堆分为最大堆，最小堆，根据顶层元素来划分
// 2. 堆也是一个二叉树
// ====================
// === heap maximum ===
// ====================
const source = [5, 1, 7, 8, 3, 2, 0, 9, 6, 4];
// 5
// / \
// 1 7
// / \ / \
// 8 [3] 2 0
// / \ /
// 9 6 4
// 上面明显不是一个最大堆，最大堆特性
// 1. 顶层元素为最大啊
// 2. 两个子元素都比父节点小
// 这里的[3]是一个特殊元素，在他以前的元素都存在子节点，在他之后的元素都没有子节点
// 注意，二叉树在数组里面的序号要保持为
// 0
// / \
// 1 2
// / \ / \
// 3 4 5 6
// / \ /
// 7 8 9
// === 第i个元素关系式
// 1. 左节点 2 * i + 1
// 2. 右节点 2 * i + 2
function swap(arr, i, j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[j] ^ arr[i];
arr[i] = arr[i] ^ arr[j];
}
/**
* 构建一个最大堆其实分步骤
* 1. 由于叶子节点无需进行父子交换，因此，可以从第一个没有叶子节点的元素开始，依次往前遍历
* 2. 每一次遍历就是调整当前元素的父子元素大小关系的过程
* @param {*} arr
* @param {*} start
*/
function maxHeapFromArray(arr) {
const length = arr.length;
let i = Math.floor(arr.length / 2);
for (; i >= 0; i -= 1) {
step();
}
/**
* 一次遍历，实际上是从i节点开始，依次考察他的子节点
* 存在比arr[currentIndex]大值的数，会被交换到arr[currentIndex]
* 因此执行一次step后，i为根的二叉树里面，arr[i]是最大值
* 这样就能保证，递归到顶层时，从上往下能满足最大堆的特性
* @param {*} currentIndex 当前节点缓存
*/
function step() {
let currentIndex = i;
// 缓存当前值
const value = arr[currentIndex];
// left 2 * i + 1;
// right 2 * i + 2;
// 依次下沉考察节点值，从左节点开始
for (let j = currentIndex * 2 + 1; j < length; j = j * 2 + 1) {
// 存在右节点，且右节点大于左节点
if (j + 1 < length && arr[j] < arr[j + 1]) {
j++;
}
// 子节点比父节点大
// 子节点数据上浮，currentIndex下沉(currentIndex实际上代表最初那个数)
if (arr[j] > value) {
arr[currentIndex] = arr[j];
currentIndex = j;
} else {
// 父节点比子节点大，跳出循环
break;
}
}
// currentIndex实际上被交换到最小位置
arr[currentIndex] = value;
}
return arr;
}
console.log(maxHeapFromArray(source));
// input [5, 1, 7, 8, 3, 2, 0, 9, 6, 4];
// output [9, 8, 7, 6, 4, 2, 0, 1, 5, 3];
// | 5 | | 9 |
// | / \ | | / \ |
// | 1 7 | | 8 7 |
// | / \ / \ | ===> | / \ / \ |
// | 8 3 2 0 | | 6 4 2 0 |
// | / \ / | | / \ / |
// | 9 6 4 | | 1 5 3 |