堆排序算法

啊噢,又开始写算法学习的笔记了。最近在准备面试的过程中又把这些常见的排序算法拿出来复习复习,既然这篇写到了堆排序,那么就代表堆排序算法的概念被我忘的差不多了,写篇博客加深记忆吧。

在维基百科上看堆排序,上面有这么一张图,

可是原谅我概念真的忘的差不多了,所以理解不了这张图,于是我又找到另一个可视化的过程,一目了然,是别人放在github page上的一个页面,地址就在这里。所以本篇文章的堆排序的可视化动画,就参考这个吧。

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于(或者大于)它的父节点。

通常堆是通过一维数组来实现的,在数组起始位置为0的情形中来看看堆节点的一些定义。

  • 父节点i的左子节点在位置(2i + 1);
  • 父节点i的右子节点在位置(2i + 2);
  • 子节点i的父节点在floor((i - 1) / 2);

关于堆中节点的位置,有如上三个定义。

在堆的数据结构中,堆中的最大值总是位于根节点上。而堆中的一个很重要的操作就是最大堆调整(Max_Heapify),即为将堆的末端子节点作调整,使得子节点永远小于父节点。

接下来看看这个关键的Max_Heapify最大堆调整的实现是怎样的:

  maxHeapify(start, end) {
    // 建立父节点指标和子节点指标
    let dad = start;
    let son = dad * 2 + 1;

    // 若子节点指标超过范围,则直接跳出函数
    if (son >= end)
      return;
    // 先比较两个子节点的大小 选择最大的
    if (son + 1 < end && this.array[son] < this.array[son + 1])
      son++;
    // 如果父节点小于子节点,交换父子节点的内容再继续子节点与孙节点的比较
    if (this.array[dad] < this.array[son]) {
      this.swap(dad, son);
      this.maxHeapify(son, end);
    }
  }

在进行最大堆调整的操作时,我们传入初始和终止的两个索引,并且根据我们刚提到的堆节点的定义,建立父节点和子节点指标。接下来如果子节点的指标超过的终止索引的范围,则直接跳出函数。否则的话我们比较两个子节点的大小,选择大的节点进行接下来的操作。

在两个节点中选取完较大节点后,我们比较父节点与子节点,如果父节点小于子节点,那么交换父子节点的内容,再递归的比较子节点与孙节点,直到调整完成。

完整的堆排序算法(javascript实现)如下:

/**
 *  堆排序算法
 */
class HeapSort {
  constructor(originalArray) {
    // 拷贝数组,不修改原数组
    this.array = [...originalArray];
  }

  swap(i, j) {
    const temp = this.array[i];
    this.array[i] = this.array[j];
    this.array[j] = temp;
  }

  maxHeapify(start, end) {
    // 建立父节点指标和子节点指标
    let dad = start;
    let son = dad * 2 + 1;

    // 若子节点指标超过范围,则直接跳出函数
    if (son >= end)
      return;
    // 先比较两个子节点的大小 选择最大的
    if (son + 1 < end && this.array[son] < this.array[son + 1])
      son++;
    // 如果父节点小于子节点,交换父子节点的内容再继续子节点与孙节点的比较
    if (this.array[dad] < this.array[son]) {
      this.swap(dad, son);
      this.maxHeapify(son, end);
    }
  }

  sort() {
    const len = this.array.length;
    // 初始化 i从最后一个父节点开始调整
    for (let i = Math.floor((len - 1) / 2); i >= 0; i--)
      this.maxHeapify(i, len);
    // 先将第一个元素和已排好的前一位做交换,再重新调整,直到排序完成
    for (let i = len - 1; i > 0; i--) {
      this.swap(0, i);
      this.maxHeapify(0, i);
    }

    return this.array;
  }
}

const array = [0, 9, 1, 8, 2, 7, 3, 6, 5, 4];
let heap = new HeapSort(array);
let res = heap.sort();
console.log(res);

sort函数里的两个for循环也要解释一下,第一个for循环,是堆的初始化,从最后一个父节点开始,调整整个数组的排序。而第二个for循环,是把第一个已经确定大小的元素和已经排好位的前一个元素做交换,再重新调整排序,直到整个排序完成。待for循环完成之后,整个数组也就呈从小到大的顺序了排好了。

理解完代码之后,再看看堆排序的时间复杂度,堆排序的平均时间复杂度,以及最优、最坏的时间复杂度都是O(nlog n),而空间复杂度是O(1),并且堆排序是一种不稳定排序。

文章中的源码在这里堆排序算法源码

Search

    Table of Contents