排序算法:堆排序的理解与实现

前言

堆排序相比冒泡排序、选择排序、插入排序而言，排序效率是最高的，本文从堆的属性和特点出发采用图文形式进行讲解并用JavaScript将其实现，欢迎各位感兴趣的开发者阅读本文😝

堆属性

堆分为两种: 最大堆和最小堆，两者的差别在于节点的排序方式。

在不同类型的堆中，每一个节点都遵循堆的属性，下方所述内容即为堆的属性。

最大堆: 父节点的值大于子节点的值
最小堆: 父节点的值小于子节点的值

由一个完全二叉树组成，且树中的所有节点都满足堆属性，这个完全二叉树就是堆。

根据堆的属性可知:

堆的根节点中存放的是最大或最小元素，但是其他节点的排列顺序是未知的。
例如，在一个最大堆中，最大的那一个元素总是位于index0的位置，但是最小的元素则未必是最后一个元素，唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。

最大堆根节点中的元素一定是树中的最大值
最小堆根节点中的元素一定是树中的最小值

数组实现堆

用数组来实现堆，堆中的节点在数组的位置与它的父节点以及子节点的索引之间有一个映射关系。

用公式来描述当前节点的父节点和子节点在数组中的位置（i为当前节点的索引）

//  父节点的位置，向下取整(floor)
parent(i) = floor( i - 1 ) / 2)
// 左子节点的位置
left(i) = 2i +1
// 右子节点的位置，左右节点总是处于相邻的位置
right(i) = left(i)+1 = 2i+2

若计算出的索引不是一个有效的数组索引(小于0时)，则当前节点没有父节点
若计算出的索引大于数组的长度，则当前节点没有子节点。
父节点的值一定大于等于其子节点的值，即:

array[parent(i)] >= array[i]

当前层级所有的节点未填满之前不允许开始下一层的填充

堆属性计算

堆是一个完全二叉树，树的高度是指从树的根节点到最低叶节点所需要的步数。

树高度正式的定义: 节点之间的边的最大值。

一个高度为h的堆有h+1层。
如果一个堆有n个节点，那么它的高度为 floor(log2(n))

// 例如，一个堆有15个节点，求这个堆的高度
h = floor(log2(15)) = floor(3.91) = 3
套入公式可得，堆的高度为3
// log2(n)，log为求次方运算，log以2为底，15的对数。若n为8，则运算结果为3，即2^3=8

如果最下面一层已经填满，那这一层的节点为 2^h个。

// 高度为3，即最下面一层有8个节点
2^3 = 8;

最下面已经填满的那一层以上的所有节点数目为 2^h -1个。

// 高度为3，即其他层的所有节点有7个
2^3 -1 = 7;

整个堆中的节点数为: 2^(h+1)-1

// 高度为3,即堆中的节点数为15
2^4 -1 = 16 - 1 = 15;

叶结点总是位于数组的floor(n/2)和n-1之间

用JS实现堆排序

实现堆排序之前，我们需要先将即将排序的数据构建成一个最大堆，构建完成后，根据最大堆的属性可知，堆顶部的值最大，我们将它取出，然后重新构建堆，直到堆中的所有数据被取出，堆排序也就完成了。

调整完全二叉树中的树为一个最大堆

在一个完全二叉树中，从一个节点出发，找到它的左子树和右子树，将当前节点与它的两颗子树进行大小比较，找到两颗树中较大的一方，将其与当前节点进行交换，交换完毕后，当前节点所在的树就是一个最大堆。我们称这个交换操作为heapify

接下来，我们来整理下实现思路

声明一个函数，参数为: 树，树的节点数，当前要进行heapify操作的节点
根据数组实现堆中所讲的，父节点和子节点在数组中位置的计算公式，找到当前节点的左子树和右子树的位置
假设最大值为当前要操作的节点，将最大值与左子树和右子树分别进行大小比较
进行大小比较后，如果最大值的位置不是当前操作节点的位置，则将其与当前操作节点位置的数据进行互换，递归调用heapify函数
退出递归: 当前操作的节点大于等于树的总节点数时，则退出递归。
当前节点与左子树和右子树进行大小比较时，如果左、右子树的位置大于树的总节点数时，不禁笑最大值赋值。

接下来我们将上述思路转化为代码：

/*
* 1. 从一个节点出发
* 2. 从它的左子树和右子树中选择一个较大值
* 3. 将较大值与这个节点进行位置交换
* 上述步骤,就是一次heapify的操作
* */

// n为树的节点数，i为当前操作的节点 (找到这颗树里的最大节点)
const heapify = function (tree, n, i) {
    if(i >= n){
        // 结束递归
        return;
    }
    // 找到左子树的位置
    let leftNode = 2 * i + 1;
    // 找到右子树的位置
    let rightNode = 2 * i +2;

    /*
       1. 找到左子树和右子树位置后，必须确保它小于树的总节点数
       2. 已知当前节点与它的左子树与右子树的位置，找到最大值
    */
    // 设最大值的位置为i
    let max = i;
    // 如果左子树的值大于当前节点的值则最大值的位置就为左子树的位置
    if(leftNode < n && tree[leftNode] > tree[max]){
        max = leftNode;
    }
    // 如果右子树的值大于当前节点的值则最大值的位置就为右子树的位置
    if(rightNode < n && tree[rightNode] > tree[max]){
        max = rightNode;
    }

    /*
    * 1. 进行大小比较后，如果最大值的位置不是刚开始设的i，则将最大值与当前节点进行位置互换
    * */
    if(max !== i){
        // 交换位置
        swap(tree,max,i);
        // 递归调用，继续进行heapify操作
        heapify(tree,n,max)
    }
};

// 交换数组位置函数
const swap = function (arr,max,i) {
    [arr[max],arr[i]] = [arr[i],arr[max]];
};

接下来我们测试下heapify函数

const dataArr = [23,15,34,11,23,4,19,80];
// 我们假设当前操作节点为数组的0号元素，我们对0号元素进行一次heapify才做
heapify(dataArr,dataArr.length,0);
// 打印结果
console.log(dataArr);

执行结果如下，观察执行结果，我们发现，0号元素所在的树符合最大堆的属性

将乱序数据构建成一个堆

通常情况下，我们的数据是乱序的，没有规律可言，此时我们就需要将这些数据构建成堆，heapify实现堆的构建前提是:知道当前操作节点的位置，此时我们从数据的最后一个节点的父节点出发，进行heapify操作，直至当前操作节点为数组的0号元素时，那么这组数据就成了一个最大堆。

接下来，我们整理下实现思路：

找到树的最后一个节点
根据数组实现堆中所讲的，寻找父节点位置的公式，根据公式我们就可以找到当前操作节点的父节点
从树最后一个节点的父节点开始进行heapify操作,直至当前操作节点为0

接下来，我们将上述思路转化为代码:

/*
* 将完全二叉树构建成堆
* 1. 从树的最后一个父节点开始进行heapify操作
* 2. 树的最后一个父节点 = 树的最后一个子结点的父节点
* */
const buildHeap = function (tree,n) {
    // 最后一个节点的位置 = 数组的长度-1
    const lastNode = n -1;
    // 最后一个节点的父节点
    const parentNode = Math.floor((lastNode - 1) / 2);
    // 从最后一个父节点开始进行heapify操作
    for (let i = parentNode; i  >= 0; i--){
        heapify(tree, n, i);
    }
};

接下来我们测试下buildHeap函数

const dataArr = [23,15,34,11,23,4,19,80];
buildHeap(dataArr,dataArr.length);
console.log(dataArr);

观察执行结果，我们发现数组中的数据已经满足最大堆的属性

实现堆排序

我们将最大堆构建完成后，根据最大堆的特性可知：堆的顶点为这个堆的最大值，我们将这个值取出，然后将堆的最后一个节点移动至堆的顶部，然后调用heapify，重新构建堆，直至最大堆中的数据全部被取出则排序完成。