堆（二叉树）排序（Heap Sort）

介绍

堆排序（Heap Sort）是一种基于堆数据结构的比较排序算法。堆是一种特殊的二叉树数据结构， 分为最大堆和最小堆。在最大堆中，父节点的值都大于或等于其子节点的值；在最小堆中， 父节点的值都小于或等于其子节点的值。堆排序通常使用最大堆进行升序排序，使用最小堆则可以降序排序。

空间复杂度解释

我这里的实现使用的是比较容易理解的递归堆排序，需要额外的栈空间 O(log n);

动画模拟

工作原理

堆排序的核心思想是利用堆这种结构，每次将堆顶元素（最大或最小）取出，然后调整剩余的堆，直到所有元素都被排好序。具体步骤如下：

• 构建最大堆： 将无序数组调整为一个符合最大堆性质的结构。从最后一个非叶子节点开始，自底向上依次调整每个节点，使其符合最大堆的性质。
• 取出堆顶元素： 将最大堆的根节点（即最大值）与最后一个节点交换，并把最大值放在数组末尾。此时，最大值已在正确的位置。
• 重新调整堆： 去掉已排好的元素，重新调整剩下的部分，使其再次成为一个最大堆。
• 重复步骤： 继续取出堆顶元素并重新调整堆，直到堆中只剩下一个元素，排序完成。

算法特性

• 时间复杂度： 堆排序的时间复杂度为O(n log n)，其中n是待排序元素的数量。这个复杂度在最好、最坏和平均情况下都是一致的，因此堆排序的性能是稳定的。
• 空间复杂度： 堆排序的空间复杂度为O(1)，因为它只需要一个与待排序元素数量相等的数组空间，不需要额外的辅助空间。
• 原地排序： 堆排序是一种原地排序算法，不需要额外的存储空间来存储待排序的元素。
• 不稳定性： 堆排序是一种不稳定的排序算法，因为相同元素的相对位置可能会因为堆的调整而发生变化。
• 适用性： 堆排序在处理大规模数据集时具有显著的优势，因为它在构建堆和调整堆的过程中是逐步进行的，不需要像快速排序那样递归地划分数据。此外，堆排序还可以作为优先级队列的基础，实现高效的插入、删除和获取操作。

源码

<script setup lang="ts">
import SortBarChart from "../comp/sort-bar-chart.vue";
import { ref } from "vue";
import { genRandArray, sortExchangeReact } from "../sort.util";
import { sleep } from "../../../utils/cmm.util";

const data = ref<number[]>(genRandArray(1, 100, 100));

const refreshData = () => {
  data.value = genRandArray(1, 100, 100);
};

const stepInterval = ref<number>(20);
const actives = ref<number[]>([]);

/**
 * 堆排序开始
 */
const sort = async () => {
  // 构造堆
  await build(0, data.value.length - 1, true);
  for (let end = data.value.length - 1; end > -1; end--) {
    // 重排堆（因为第一个元素和最后一个元素交换位置）
    await build(0, end);
    // 第一个元素和最后一个元素交换位置
    sortExchangeReact(data.value, 0, end);
  }
};

/**
 * 重排堆
 * @param pos 当前位置
 * @param end 结束位置
 * @param isBuild 是否为构造堆模式
 */
const build = async (pos: number, end: number, isBuild = false) => {
  if (pos > end) return;
  const left = pos * 2 + 1;
  const right = left + 1;
  if (isBuild) {
    await build(left, end, true);
    await build(right, end, true);
  }
  actives.value = [pos, left > end ? pos : left, right > end ? pos : right];
  await sleep(stepInterval.value);
  const max = maxPos(actives.value, end);
  if (max != pos) {
    sortExchangeReact(data.value, pos, max);
    await build(max, end);
  }
};

/**
 * 从位置数组中找出最大值对应的位置
 * @param pos 位置列表
 * @param end  结束位置
 */
const maxPos = (pos: number[], end: number) => {
  let res = pos[0];
  pos.forEach(p => {
    if (p > end || p >= data.value.length) return;
    if (data.value[res] < data.value[p]) res = p;
  });
  return res;
};
</script>

<template>
  <div class="">
    <a-space direction="horizontal">
      <a-input-number v-model="stepInterval" :step="50" :min="5" style="width: 200px">
        <template #suffix>ms</template>
        <template #prefix> 步进间隔</template>
      </a-input-number>
      <a-button @click="sort()">开始排序</a-button>
      <a-button @click="refreshData">刷新数据</a-button>
    </a-space>
    <div class="mt-sm" style="height: 300px">
      <sort-bar-chart :data="data" :actives="actives" />
    </div>
  </div>
</template>

<style scoped lang="less"></style>