堆与堆排序

堆与堆排序

​ 堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值
• 堆总是一棵完全二叉树

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。本篇博文我们来使用JavaScript来构建一个堆，并实现堆排序。

一、最大堆

​ 根节点大于等于其叶子节点的堆被称为最大堆。虽然堆是一个树形结构，但是考虑到它是一个完全二叉树，有一个经典的实现就是使用数组来模拟。

/**
 * 最大堆
 */
class MaxHeap {
    constructor (n) {
        this.arr = []; // 模拟堆
        this.count = 0; // 堆中元素数量
        this.capacity = n; // 堆最大容量
    }

    insert (e) {
        if (this.count >= this.capacity) {
            throw new RangeError('堆中空间已满！');
        }
        this.arr[this.count] = e;
        this._shiftUp(this.count);
        this.count++;
    }

    extractMax () {
        if (this.count <= 0) {
            throw new RangeError('堆中已无元素！');
        }
        let maxElement = this.arr[0];
        this._swapArr(this.arr, 0, this.count - 1);
        this.count--;
        this._shiftDown(0);
        return maxElement;
    }

    _shiftUp (k) {
        while ((k - 1) >> 1 >= 0 && this.arr[k] > this.arr[(k - 1) >> 1]) {
            this._swapArr(this.arr, k, (k - 1) >> 1);
            k = (k - 1) >> 1;
        }
    }

    _shiftDown (k) {
        while (2 * k + 1 < this.count) {
            let j = 2 * k + 1;
            if (j + 1 < this.count && this.arr[j + 1] > this.arr[j]) {
                j++;
            }
            if (this.arr[j] <= this.arr[k]) {
                break;
            }
            this._swapArr(this.arr, j, k);
            k = j;
        }
    }

    _swapArr (arr, m, n) {
        let temp = arr[m];
        arr[m] = arr[n];
        arr[n] = temp;
    }
}

二、最小堆

​ 根节点小于等于其叶子节点的堆被称为最大堆。

/**
 * 最小堆
 */
class MinHeap {
    constructor (n) {
        this.arr = []; // 模拟堆
        this.count = 0; // 堆中元素数量
        this.capacity = n; // 堆最大容量
    }

    insert (e) {
        if (this.count >= this.capacity) {
            throw new RangeError('堆元素已满！');
        }
        this.arr[this.count] = e;
        this._shiftUp(this.count);
        this.count++;
    }

    extractMin () {
        if (this.count <= 0) {
            throw new RangeError('堆已经为空！');
        }
        let result = this.arr[0];
        this._swap(0, this.count - 1);
        this.count--;
        this._shiftDown(0);
        return result;
    }

    _shiftDown (k) {
        while (2 * k + 1 < this.count) {
            let j = 2 * k + 1;
            if (j + 1 < this.count && this.arr[j + 1] < this.arr[j]) {
                j++;
            }
            if (this.arr[k] <= this.arr[j]) {
                break;
            }
            this._swap(k, j);
            k = j;
        }
    }

    _shiftUp (k) {
        while ((k - 1) >> 1 >= 0 && this.arr[k] < this.arr[(k - 1) >> 1]) {
            this._swap(k, (k - 1) >> 1);
            k = (k - 1) >> 1;
        }
    }

    _swap (m, n) {
        let temp = this.arr[m];
        this.arr[m] = this.arr[n];
        this.arr[n] = temp;
    }
}

三、堆排序

​ 堆排序就是使用了堆这种数据结构的思想，来优化排序速度的。

// 使用上面的最大堆的类来进行排序
function maxHeapSort (arr) {
    let heap = new MaxHeap(arr.length);
    arr.forEach(v => {
        heap.insert(v);
    });
    for (let i = arr.length - 1; i >= 0; i--) {
        arr[i] = heap.extractMax();
    }
}

// 使用上面最小堆的类来进行排序
function minHeapSort (arr) {
    let heap = new MinHeap(arr.length);
    arr.forEach(v => {
        heap.insert(v);
    });
    for (let i = 0; i < arr.length; i++) {
        arr[i] = heap.extractMin();
    }
}

​ 对于以上堆排序的方法，我们是否可以考虑优化呢？答案当然是肯定的，在上面的堆排序算法中，我们额外使用一个空间为n的辅助堆，往这个堆中插入以及取出数据的时间复杂度都是O(nlogn)。通过查阅资料和学习我们可以知道，我们在进行堆排序时，我们并不需要辅助空间，直接在原地构建一个heap即可，这个行为过程有一个专有的名称叫做Heapify。

// 原地堆排序
function heapSort (arr) {
    // heapify
    for (let i = (arr.length - 1 - 1) >> 1; i >= 0; i--) {
        shiftDown(arr, i, arr.length);
    }
    // 排序
    for (let i = arr.length - 1; i > 0; i--) {
        swapArr(arr, 0, i);
        shiftDown(arr, 0, i);
    }
}
// 优化shiftDown,对比之前的代码，减少swap，改为直接赋值
function shiftDown (arr, i, n) {
    let temp = arr[i];
    while (2 * i + 1 < n) {
        let j = 2 * i + 1;
        if (j + 1 < n && arr[j + 1] > arr[j]) {
            j++;
        }
        if (temp >= arr[j]) {
            break;
        }
        arr[i] = arr[j];
        i = j;
    }
    arr[i] = temp;
}