【经典排序算法】堆排序

[Enivia]

堆排序

堆总是满足以下性质：

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

将根结点最大的堆叫做最大堆/大根堆，根结点最小的堆叫做最小堆/小根堆。

堆排序的核心就是小根堆/大根堆的构造。

原理

以升序为例，具体流程为：

1. 将待排序的序列构造为小根堆
2. 取走根节点，即为最小值
3. 继续将剩余节点构造为小根堆后重复上述操作，直到排序完成

图解

初始无序数组 [8, 4, 5, 7, 1, 3, 2, 6, 9]，对应的树结构如下

下面开始构造最小堆。找到最后一个非叶子节点，从左到右与其子节点进行比较，若比其子节点大，则进行交换。

完成后，找到倒数第二个非叶子节点，继续排序。

对所有根节点重复上述操作。

排序过程

代码实现

以构造最大堆为例：

function swap(arr, i, j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

/** 调整堆结构 */
function minHeapify(arr, index, size) {
  var left = index * 2 + 1;
  var right = index * 2 + 2;
  var root = index;

  if (left < size && arr[left] < arr[root]) {
    root = left;
  }
  if (right < size && arr[right] < arr[root]) {
    root = right;
  }
  if (root !== index) {
    swap(arr, root, index);
    minHeapify(arr, root, size);
  }
}

/** 构造最小堆 */
function buildMinHeap(arr, size) {
  var start = Math.floor(size / 2) - 1;
  for (var i = start; i >= 0; i--) {
    minHeapify(arr, i, size);
  }
}

/** 排序 */
function sort(nums) {
  const result = []
  let len = nums.length;
  buildMinHeap(nums, len);
  for (let i = len - 1; i >= 0; i--) {
    swap(nums, i, 0);
    result.push(nums[len - 1]);
    len -= 1;
    buildMinHeap(nums, len);
  }
  return result
}