排序算法:堆排序——JavaScript及Java实现

语言: CN / TW / HK

完整代码

堆的概念

一般堆排序里的堆指的是二叉堆,是一种完全二叉树。完全二叉树有一个性质是,除了最底层,每一层都是满的,这使得堆可以利用数组来表示,每个结点对应数组中的一个元素。

二叉堆有两种: 最大堆和最小堆 。最大堆所有父节点的值大于子节点的值,最小堆所有父节点的值小于子节点的值。

显然,最大堆堆顶元素必然是堆中最大的元素,最小堆堆顶元素是堆中最小的元素

堆排序实现

下面使用 JavaScript 代码介绍堆排序实现。

首先需要初始化一个二叉堆,前面介绍了二叉堆实际上就是一个数组,因此初始化非常简单:

constructor(arr) {
    this.data = [...arr];
    this.size = this.data.length;
}

在初始化的时候,如果某一结点不符合二叉堆的性质,需要将该节点与两个子节点进行交换。具体流程是,当前节点与两个子节点进行对比,如果不符合二叉堆性质,取三个里面的最大值并进行交换,交换后的子节点继续递归进行后续子树的交换:

maxHeapify(i) {
    let max = i; // 保存最大的节点下标

    if (i >= this.size) return;

    const left = i * 2 + 1; // 左节点下标
    const right = i * 2 + 2; // 右节点下标

    if ((left < this.size) && (this.data[left] > this.data[max])) {
        max = left;
    }

    if ((right < this.size) && (this.data[right] > this.data[max])) {
        max = right;
    }

    if (max === i) return; // 如果最大节点是其本身,不进行交换

    [this.data[i], this.data[max]] = [this.data[max], this.data[i]];

    return this.maxHeapify(max);
}

关键代码:

const left = i * 2 + 1; // 获取左节点

const right = i * 2 + 2; // 获取右节点

上面的maxHeapify函数只能对某一结点进行对调,无法对整个数组进行重构。构造一个最大堆需要获取到所有的分支节点(不含叶子节点),然后对每个分支节点依次进行递归重构:

rebuildHeap() {
    // 获取分支节点
    const L = Math.floor(this.size / 2);
    for(let i = L - 1; i >= 0; i--){
        // 每个i都代表一个分支节点的下标
        this.maxHeapify(i);
    }
}

关键代码:

注意上一步完成后数组还并没有完成排序,只是基本有序,下面进行排序操作。从最后一个元素开始,和堆顶元素交换,然后size-1将最后一个元素分离出堆,调用maxHeapify维持最大堆性质。由于堆顶元素必然是堆中最大的元素,所以一次操作之后,堆中存在的最大元素被分离出堆,重复n-1次之后,数组排列完毕:

sort() {
    for(let i = this.size - 1; i > 0; i--){
        [this.data[0], this.data[i]] = [this.data[i], this.data[0]];
        this.size--; // 将交换后的元素分离出堆
        this.maxHeapify(0);
    }
    this.size = this.data.length; // 排序完成后重新获取size
}

如果是从小到大排序,用最大堆;从大到小排序,用最小堆

时间复杂度与稳定性

一道面试题

分享到: