My Muri Life

切换主题

本页目录

堆排序 ​

基本思想：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

算法过程描述：

  1. 初始化堆（以大顶堆为例）len = A.length：
    1. 从第一个非叶节点i = (len >> 1) - 1开始初始化大顶堆;
    2. 首先从root=A[i]、A[idxL=2*i+1]、A[idxR=idxL+1]子树中找出最大值，并将其交换至根节点A[i]处；
    3. 以idxL=2*idxL+1为步进，在idxL<len内重复步骤1.2；
    4. 重复步骤1.1至步骤1.3直到建堆完成。
  2. 排序：
    1. 此时的堆顶根节点（即A[0]）为整个序列的最大值；
    2. 将其与末尾元素A[--len]进行交换，此时末尾就为最大值;
    3. 然后将剩余len个（此时的len已减一）元素重新构造成一个大顶堆，此时得到整个序列的次大值；
    4. 重复步骤2.1至步骤2.3，直到len===1时，便可得到整个序列的递增序列。

大顶堆 ​

JavaScript
const heapSort = A => {
  let len = A.length

  const heapify = (A, i, len) => {
    let root = A[i] // 根节点
    // 左子节点下标 idxL = 2 * i + 1
    for (let j = 2 * i + 1; j < len; j = 2 * j + 1) {
      root = A[i]
      // 右子节点下标 idxR = 2 * i + 2
      if (j + 1 < len && A[j + 1] > A[j]) {
        j++ // 右子节点有效且 A[idxR]大于A[idxL]
      }
      if (A[j] > root) { // 右子节点 大于 根节点
        [A[i], A[j]] = [A[j], A[i]]
        i = j // 更新最大值下标
      } else {
        break
      }
    }
  }

  // 从第一个非叶节点 (len>>1) -1，开始初始化大顶堆
  for (let i = (len >> 1) - 1; i >= 0; i--) {
    heapify(A, i, len)
  }
  // 排序
  while (len-- > 1) {
    [A[0], A[len]] = [A[len], A[0]]
    heapify(A, 0, len)
  }
}

小顶堆 ​

JavaScript
// 仅修改两行代码
const heapSort = A => {
  let len = A.length

  const heapify = (A, i, len) => {
    let root = A[i]
    for (let j = 2 * i + 1; j < len; j = 2 * j + 1) {
      root = A[i]
      if (j + 1 < len && A[j + 1] < A[j]) {
        j++
      }
      if (A[j] < root) {
        [A[i], A[j]] = [A[j], A[i]]
        i = j
      } else {
        break
      }
    }
  }

  for (let i = (len >> 1) - 1; i >= 0; i--) {
    heapify(A, i, len)
  }

  while (len-- > 1) {
    [A[0], A[len]] = [A[len], A[0]]
    heapify(A, 0, len)
  }
}

算法应用 ​

leetcode
  1. 剑指 Offer 40. 最小的k个数