排序之堆排序与 JavaScript 实现

成堆 `Heapify`

对于一个给定的数组，我们不一定实现堆这个类，而是通过 成堆 (Heapify) 这样的操作来使得数组具有堆的性质。

如图所示，要使得这个数组所对应的完全二叉树形成一个最大堆，只需要使得每一棵子树都形成最大堆即可。那么不难看出，所有的叶子结点都可以看作是一个仅有一个元素的最大堆，所以我们只需要从最后一个非叶子结点开始，通过前一节的 shiftDown 操作，就可以很容易的构建出最大堆来。

一个显而易见的数学关系是：完全二叉树最后一个非叶子节点的索引是 $n\div {2}$，例如这里有 10 个元素，那么最后一个非叶子结点的索引就是 5；类似的，如果有 11 个元素，那么同样 5 是最后一个非叶子结点的索引；不过要注意的是，这里的索引是从 1 开始的，如果是从 0 开始的索引只需使 i-1 ($n\div {2}-1$) 即可。这很容易就能用数学归纳法证明。

简单来说，Heapify 的算法过程可以简述为:

从最后一个非叶子结点开始向前遍历数组；
每遇到一个非叶子结点，就通过 shiftDown 使以当前节点为根结点的子树成最大堆；
重复直到根节点完成 shiftDown。

动画演示:

示例代码

const { PrintableMaxHeap } = require('./02-Max-Heap-Class-Basic')

//heapSort1, 将所有的元素依次添加到堆中，在将所有元素从堆中依次取出来，即完成了排序 
// 无论是创建堆的过程，还是从堆中依次取出元素的过程，时间复杂度均为 O (nlogn)
// 整个堆排序的整体时间复杂度为 O (nlogn)
exports.heapSort1 = array => {
  const n = array.length
  const maxHeap = new PrintableMaxHeap(n)
  for (const i of array) {
    maxHeap.insert(i)
  }
  for (let i = n - 1; i >= 0; i--) {
    array [i] = maxHeap.extractMax()
  }
  return array
}

//heapSort2, 借助我们的 heapify 过程创建堆 
// 此时，创建堆的过程时间复杂度为 O (n), 将所有元素依次从堆中取出来，时间复杂度为 O (nlogn)
// 堆排序的总体时间复杂度依然是 O (nlogn), 但是比上述 heapSort1 性能更优，因为创建堆的性能更优 
exports.heapSort2 = array => {
  const n = array.length
  const maxHeap = new PrintableMaxHeap(array, n)
  for (let i = n - 1; i >= 0; i--) {
    array [i] = maxHeap.extractMax()
  }
  return array
}

class MaxHeap {
  // 新的构造函数，传入一个数组使其成最大堆 
  constructor (array) {
    const n = array.length
    this.#data = new Array(n + 1)
    this.#capacity = n
    for (let i = 0; i < n; i++) {
      this.#data [i + 1] = array [i]
    }
    this.#count = n
    for (let i = Math.floor(n / 2); i >= 1; i--) {
      shiftDownEnhance(this.#data, i, n)  // 见【慕课】重学算法 - part.3 堆排序 (1)
    }
  }
  ...
}

通过堆进行排序

通过新的构造函数，我们可以方便的将一个数组构造为最大堆，显而易见的，我们将数组放入再取出最大堆的过程，其实就完成了一次排序。我们可以这样实现:

/**
 * generateRandomArray @see https://github.com/Mitscherlich/Play-with-Algorithms-JS/blob/master/test/utils/index.js#L8
 */
const sorted = []
const array = generateRandomArray(50, 0, 100)
const maxHeap = new MaxHeap(array.slice())
while (!maxHeap.isEmpty()) {
  sorted.unshift(maxHeap.extractMax())
}
console.log(JSON.stringify(sorted))

值得注意的是，这种通过 Heapify 来成堆的操作并进行堆排序速度由于上一节我们一个一个将元素插入进堆的操作，事实上，这两种操作的算法复杂度的确有所不同的：

将 n 个元素注意插入空堆中：$O (nlog {n})$
Heapfiy：$O (n)$

由于堆算法复杂度的证明不是本系列的重点并且有点难，感兴趣的同学可以自己来进行详细地推导证明，这里并不展开。

数组的原地堆排序

无论是将元素逐一插入空堆还是通过 Heapify 来使数组成堆，我们实际上都开辟了一个堆的空间 (也就是使用了额外的 $O (n)$ 的空间复杂度)。但结合上面 Heapify 的思想，我们也可以很容易的改造堆排序的过程，使数组原地完成堆排序的操作。

一个已经形成最大堆的数组

我们假定通过 Heapify 已经使一个数组形成最大堆，这时数组中第一个元素也就是最大的元素，要是数组从小到大排序，只需使现在数组第一个位置的元素与最后一个元素交换位置：

而此时由于 w 并不一定是最大元素，也就使得原有最大堆的性质遭到了破坏。这时只需通过对 w 元素进行一次 shiftDown 操作，就能使数组的前部重新形成最大堆：

那么重复上述操作就可以使整个数组完成排序。

示例代码

const shiftDown = (array, n, k) => {
  while (2 * k + 1 < n) {
    let j = 2 * k + 1
    if (j + 1 < n && array [j + 1] > array [j]) {
      j++
    }
    if (array [k] >= array [j]) {
      break
    }
    //swap (arr [k] , arr [j])
    [array [k], array [j]] = [array [j], array [k]]
    k = j
  }
}

// 不使用一个额外的最大堆，直接在原数组上进行原地的堆排序 
Array.prototype.heapSort = function () {
  const array = this.slice()
  const n = array.length
  //heapify
  // 注意，此时我们的堆是从 0 开始索引的 
  // 从 (最后一个元素的索引 - 1)/2 开始 
  // 最后一个元素的索引 = n-1
  for (let i = Math.floor((n - 1) / 2); i >= 0; i--) {
    shiftDown(array, n, i)
  }
  for (let i = n - 1; i > 0; i--) {
    //swap (arr [0], arr [i])
    [array [0], array [i]] = [array [i], array [0]]
    shiftDown(array, i, 0)
  }
  return array
}

类似的，最后使用一步交换进行优化:

// 优化的 shiftDown 过程，使用赋值的方式取代不断的 swap,
// 该优化思想和我们之前对插入排序进行优化的思路是一致的 
const shiftDownEnhance = (array, n, k) => {
  const e = array [k]
  while (2 * k + 1 < n) {
    let j = 2 * k + 1
    if (j + 1 < n && array [j + 1] > array [j]) {
      j++
    }
    if (e >= array [j]) {
      break
    }
    array [k] = array [j]
    k = j
  }
  array [k] = e
}

// 优化的堆排序 
Array.prototype.heapSortEnhance = function () {
  const array = this.slice()
  const n = array.length
  for (let i = Math.floor((n - 1) / 2); i >= 0; i--) {
    shiftDownEnhance(array, n, i)
  }
  for (let i = n - 1; i > 0; i--) {
    //swap (arr [0], arr [i])
    [array [0], array [i]] = [array [i], array [0]]
    shiftDownEnhance(array, i, 0)
  }
  return array
}

索引堆

在上面的实现的堆中，我们总是直接操作原右数组元素。这在处理基本数据或者简单类型时没有问题，但往往我们面对的数据类型并非如此。例如，我们在处理 CMS 内容时如果使用对这种结构，一旦要交换的数据量非常大，交换操作本身变得非常慢；而这种问题还可以通过技术手段解决；又例如在操作系统的进程调度时，我们可能根据进程的 pid 数组构建了最大堆来表示进程的优先级，一旦我们直接交换了堆中元素的位置，我们就无法根据新的索引找到原来的进程，也就使得 pid 和进程脱离了关系；像这种情况使用 索引堆 就更为方便。

索引最大堆示意图

示例代码

function shiftUp (data, indexes, k) {
  const e = indexes [k]
  while (k > 1 && data [indexes [Math.floor(k / 2)]] < data [e]) {
    //swap (indexes [k/2], indexes [k])
    indexes [k] = indexes [Math.floor(k / 2)]
    k = Math.floor(k /= 2)
  }
  indexes [k] = e
}

function shiftDown (data, indexes, k, count ) {
  const e = indexes [k]
  while (2 * k <= count) {
    let j = 2 * k // 此轮循环中，swap (indexes [k], indexes [j])
    if (j + 1 <= count && data [indexes [j + 1]] > data [indexes [j]]) {
      j++
    }
    if (data [e] >= data [indexes [j]]) {
      break
    }
    //swap (indexes [k], indexes [j])
    indexes [k] = indexes [j]
    k = j
  }
  indexes [k] = e
}

class IndexMaxHeap {
  // 构造函数，构造一个空堆，可容纳 capacity 个元素 
  constructor (capacity) {
    this.#data = new Array(capacity + 1)
    this.#indexes = new Array(capacity + 1)
    this.#count = 0
    this.#capacity = capacity
  }
  size () { return this.#count }
  isEmpty () { return this.#count === 0 }
  // 获取最大索引堆中的堆顶元素 
  getItem (i) { return this.#data [i + 1] }
  // 传入的 i 是从 0 开始索引的 
  insert (i, item) {
    i += 1
    this.#data [this.#count + 1] = item
    this.#indexes [this.#count + 1] = i
    this.#count++
    shiftUp(this.#data, this.#indexes, this.#count)
  }
  extractMax () {
    const ret = this.#data [this.#indexes [1]]
    //swap (data [indexes [1]], data [indexes [count]])
    ;[this.#indexes [1], this.#indexes [this.#count]] = [this.#indexes [this.#count], this.#indexes [1]]
    this.#count -= 1
    shiftDown(this.#data, this.#indexes, 1, this.#count)
    return ret
  }
  extractMaxIndex () {
    const ret = this.#indexes [1] - 1
    //swap (data [indexes [1]], data [indexes [count]])
    ;[this.#indexes [1], this.#indexes [this.#count]] = [this.#indexes [this.#count], this.#indexes [1]]
    this.#count -= 1
    shiftDown(this.#data, this.#indexes, 1, this.#count)
    return ret
  }
  // 将最大索引堆中索引为 i 的元素修改为 newItem
  change (i, item) {
    i += 1
    this.#data [i] = item
    // 找到 indexes [j] = i, j 表示 data [i] 在堆中的位置 
    // 之后 shiftUp (j), 再 shiftDown (j)
    for (let j = i; j <= this.size(); j++) {
      if (this.#indexes [j] === i) {
        shiftUp(this.#data, this.#indexes, j)
        shiftDown(this.#data, this.#indexes, j, this.#count)
        return
      }
    }
  }
}

上面这个索引堆的类不仅实现了最基本的堆的操作，还实现了一些索引堆可以完成的特殊操作；而最重要的就是 change 操作，用户可以通过给定一个索引来方便的修改堆中某个元素的值。但可以注意到，修改完这个元素后，要使得堆继续形成最大堆，我们仍需要对新插入的元素进行 shiftUp 和 shiftDown 来维持堆的性质，而这使得修改元素的复杂度变成了 $O (n+log {n}) ~ O (n)$，这与堆的插入删除元素 $O (nlog {n})$ 的复杂度并不相符，我们可以尝试建立对 索引的索引 来优化这个过程：

优化索引最大堆示意图

用 reverse 数组来表示 i 在 indexes(堆) 中的位置：

if 
	indexes [i] = j
	reverse [j] = i
then 
	indexes [reverse [i]] = i
	reverse [indexes [i]] = i

这样，我们就可以在 $O (1)$ 内找到一个索引对应的元素：

function shiftUpEnhance (data, indexes, reverse, k) {
  const e = indexes [k]
  while (k > 1 && data [indexes [Math.floor(k / 2)]] < data [e]) {
    //swap (indexes [k/2], indexes [k])
    indexes [k] = indexes [Math.floor(k / 2)]
    reverse [indexes [Math.floor(k / 2)]] = Math.floor(k / 2)
    reverse [indexes [k]] = k
    k = Math.floor(k /= 2)
  }
  indexes [k] = e
}

function shiftDownEnhance (data, indexes, reverse, k, count) {
  const e = indexes [k]
  while (2 * k <= count) {
    let j = 2 * k // 此轮循环中，swap (indexes [k], indexes [j])
    if (j + 1 <= count && data [indexes [j + 1]] > data [indexes [j]]) {
      j++
    }
    if (data [e] >= data [indexes [j]]) {
      break
    }
    //swap (indexes [k], indexes [j])
    indexes [k] = indexes [j]
    reverse [indexes [k]] = k
    reverse [indexes [j]] = j
    k = j
  }
  indexes [k] = e
}

class IndexMaxHeap {
  // 构造函数，构造一个空堆，可容纳 capacity 个元素 
  constructor (capacity) {
    this.#data = new Array(capacity + 1)
    this.#indexes = new Array(capacity + 1)
    this.#reverse = new Array(capacity + 1).fill(0) // 填入 0 使得默认的索引索引位置为 0 (总是无效的元素)
    this.#count = 0
    this.#capacity = capacity
  }
  ...
  // 传入的 i 是从 0 开始索引的 
  insert (i, item) {
    i += 1
    this.#data [this.#count + 1] = item
    this.#indexes [this.#count + 1] = i
    this.#reverse [i] = this.#count + 1
    this.#count++
    shiftUpEnhance(this.#data, this.#indexes, this.#reverse, this.#count)
  }
  extractMax () {
    const ret = this.#data [this.#indexes [1]]
    //swap (data [indexes [1]], data [indexes [count]])
    ;[this.#indexes [1], this.#indexes [this.#count]] = [this.#indexes [this.#count], this.#indexes [1]]
    this.#reverse [this.#indexes [1]] = 1
    this.#reverse [this.#indexes [this.#count]] = 0
    this.#count -= 1
    shiftDownEnhance(this.#data, this.#indexes, this.#reverse, 1, this.#count)
    return ret
  }
  extractMaxIndex () {
    const ret = this.#indexes [1] - 1
    //swap (data [indexes [1]], data [indexes [count]])
    ;[this.#indexes [1], this.#indexes [this.#count]] = [this.#indexes [this.#count], this.#indexes [1]]
    this.#reverse [this.#indexes [1]] = 1
    this.#reverse [this.#indexes [this.#count]] = 0
    this.#count -= 1
    shiftDownEnhance(this.#data, this.#indexes, this.#reverse, 1, this.#count)
    return ret
  }
  // 将最大索引堆中索引为 i 的元素修改为 newItem
  change (i, item) {
    i += 1
    this.#data [i] = item
    // 找到 indexes [j] = i, j 表示 data [i] 在堆中的位置 
    // 之后 shiftUp (j), 再 shiftDown (j)
    //for (let j = i; j <= this.size (); j++) {
    //   if (this.#indexes [j] === i) {
    //     shiftUpEnhance (this.#data, this.#indexes, j)
    //     shiftDownEnhance (this.#data, this.#indexes, j, this.#count)
    //     return
    //   }
    // }
    // 有了 reverse 之后，
    // 我们可以非常简单的通过 reverse 直接定位索引 i 在 indexes 中的位置 
    const j = this.#reverse [i]
    shiftUpEnhance(this.#data, this.#indexes, this.#reverse, j)
    shiftDownEnhance(this.#data, this.#indexes, this.#reverse, j, this.#count)
  }
}

排序总结

四大重要排序算法比较

本系列的排序算法到这里就完结了。我们一共只为大家介绍了两类七种排序算法，大家也许还知道或者学习过其他更多的排序算法，这里限于篇幅就不一一为大家介绍了。

我们主要学习的就是上图四种 基于比较的排序算法 。除了插入排序复杂度为 $O (n^2)$ 以外，其余几种排序算法复杂度均为 $O (nlog {n})$，但这也并不是说明插入排序不好，事实上我们在测试中可以发现在完全有序的数组上插入排序的复杂度退化为 $O (n)$，甚至优于同等的高级排序算法。这说明我们在编程开发时应学会结合实际情况，选择最优的排序算法，而不是只会做一个 API caller。

排序算法的稳定性

再看图中，我们看到了一个概念： 稳定排序 。这是指对于 相等的 元素，在排序前后，想等元素的 相对位置 没有发生改变。例如对一组学生成绩排序时，不仅要对成绩进行排序，还在在学生成绩想等时按姓名的字典序排序，很可能大部分时候原始数据都已经按姓名的字典序排好序了，但是快速排序和堆排序就有可能打乱原来的顺序。