Skip to content

堆排序

· 5 min

堆排序包含 3 个步骤：

  1. 用数组创建一个最大堆用作源数据。
  2. 在创建最大堆后，最大的值会被存储在堆的第一个位置。我们要将它替换为堆的最后一个值，将堆的大小减 1.
  3. 最后，我们将堆的根节点下移并重复步骤 2 直到堆的的大小为 1
utils.js
function defaultCompare(a, b) {
  if (a === b) return Compare.EQUALS
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN
}


function swap(array, a, b) {
  ;[array[a], array[b]] = [array[b], array[a]]
}
// 引入默认比较函数和交换函数
// defaultCompare(a, b): 比较函数，返回 1, 0 或 -1
// swap(array, i, j): 交换数组 array 中下标 i 和 j 位置的元素
const { defaultCompare, swap } = require('./utils.js')


/**
 * 将给定节点 (index) 以及它的左右子节点维护在最大堆的状态。
 *
 * @param {Array} array - 待维护堆的数组
 * @param {number} index - 当前要维护堆性质的节点下标
 * @param {number} heapSize - 当前堆中有效元素的数量（或边界）
 * @param {Function} compareFn - 比较函数，用于比较两个元素大小
 */
function heapify(array, index, heapSize, compareFn) {
  let largest = index // 先假设当前的节点就是最大节点的索引


  // 根据当前节点的索引计算左子节点和右子节点的下标
  const left = 2 * index + 1
  const right = 2 * index + 2


  // 接下来就需要和左右的子节点进行比较，如果比左右的子节点小，那么就要更新 largest


  // 如果左子节点存在，并且左子节点的值比当前的节点值大，就更新 largest
  if (left < heapSize && compareFn(array[left], array[index]) > 0) {
    largest = left
  }


  // 如果右子节点存在，并且右子节点的值比当前的节点值大，就更新 largest
  if (right < heapSize && compareFn(array[right], array[largest]) > 0) {
    largest = right
  }


  if (largest !== index) {
    // 如果进入此分支，说明 largest 被更新过，也就是说，子节点中有更大的值
    swap(array, index, largest)
    // 接下来继续递归的进行调整
    heapify(array, largest, heapSize, compareFn)
  }
}


/**
 * 构建最大堆。
 *
 * 原理：从最后一个非叶子节点开始，向前（即从底部到顶部）逐个调用 heapify，
 *       这样能保证堆的所有子树都满足最大堆的性质。
 *
 * @param {Array} array - 待构建最大堆的数组
 * @param {Function} compareFn - 比较函数
 * @returns {Array} 构建好的最大堆（实际上仍旧是传入的那个数组）
 * 0~ Math.floor(array.length / 2)
 */
function buildMaxHeap(array, compareFn) {
  // 从最后一个非叶子节点开始，调整结构，使其成为一个最大堆
  for (let i = Math.floor(array.length / 2); i >= 0; i--) {
    heapify(array, i, array.length, compareFn)
  }
}


/**
 * 堆排序函数。
 * 1. 先构建一个最大堆
 * 2. 不断将堆顶元素（最大值）和末尾元素互换
 * 3. 交换后减小堆的范围，重新维护堆顶，以保持最大堆性质
 *
 * 时间复杂度：
 * - 构建最大堆 O(n)
 * - 交换并维护堆 O(n log n)
 *
 * @param {Array} array - 待排序的数组
 * @param {Function} compareFn - 比较函数，默认为 defaultCompare
 * @returns {Array} - 已完成排序的数组（原地排序）
 */
function heapSort(array, compareFn = defaultCompare) {
  let heapSize = array.length // 获取堆的大小
  // 构建最大堆
  buildMaxHeap(array, compareFn)


  // 目前就已经形成了最大堆 [5, 3, 4, 1, 2]
  // 形成的最大堆，能够保证的是数组的第一个一定是最大的
  while (heapSize > 1) {
    // 1. 交换堆顶元素（数组第一个元素）和数组末尾元素
    swap(array, 0, --heapSize) // [2, 3, 4, 1, 5]
    // 2. 缩小堆的范围，重新形成最大堆
    // 注意，这里在形成新的最大堆结构的时候，最大堆的范围就已经缩小了
    // 也就是说，目前是针对 [2, 3, 4, 1] 这几个元素来形成新的最大堆
    heapify(array, 0, heapSize, compareFn)
  }
  return array
}

另外一种方式：直接构建最小堆，不断从最小堆中提取第一个元素

const { MinHeap } = require('./heap.js')
const array = [36, 27, 20, 60, 55, 7, 28, 39, 67, 44, 16]


const heap = new MinHeap() // 首先构建一个最小堆
heap.heapify(array)


const sortedArray = [] // 存储排好序后的元素
while (!heap.isEmpty()) {
  sortedArray.push(heap.extract())
}


// 上面的 while 出来之后，排序就排好了
console.log(sortedArray)

-EOF-