再谈堆排序：堆排序算法流程步骤透解—最大堆构建原理

堆排序概述

Heapsort类似于 选择排序我们反复选择最大的项目并将其移动到列表的末尾。主要的区别在于，我们不是扫描整个列表来查找最大的项目，而是将列表转换为最大堆（父节点的值总是大于子节点，反之最小堆）以加快速度。

注意：堆一定是一棵完全二叉树

先上一张堆排序动画演示图片：

图、树、二叉树、二叉堆等基本概念，一时三刻讲不完，安利下本人整理的文章

《讲透学烂二叉树一：树和图的概念以及二叉树的基本性质 》

《讲透学烂二叉树一：树和图的概念以及二叉树的基本性质》

这里摘取二叉树排序需要的重点部分，再过一遍

二叉树概述

要了解堆首先得了解一下二叉树，在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的特点

1. 二叉树的每个结点至多只有二棵子树（不存在度大于 2 的结点）
2. 二叉树的子树有左右之分，次序不能颠倒。
3. 二叉树的第 i 层至多有 2i - 1 个结点；
4. 深度为 k 的二叉树至多有 2k - 1 个结点；
5. 对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则n0 = n2 + 1。

树和二叉树的三个主要差别：

• 树的结点个数至少为 1，而二叉树的结点个数可以为 0
• 树中结点的最大度数没有限制，而二叉树结点的最大度数为 2
• 树的结点无左、右之分，而二叉树的结点有左、右之分

二叉树又分为完全二叉树（complete binary tree）和满二叉树（full binary tree）

满二叉树：一棵深度为 k，且有 2k - 1 个节点称之为满二叉树

深度为 3 的满二叉树 full binary tree

完全二叉树：深度为 k，有 n 个节点的二叉树，当且仅当其每一个节点都与深度为 k 的满二叉树中序号为 1 至 n 的节点对应时，称之为完全二叉树

深度为 3 的完全二叉树 complete binary tree

什么是堆？

堆（二叉堆）可以视为一棵完全的二叉树，完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。

如下图，是一个堆和数组的相互关系

堆和数组的相互关系

对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、孩子结点的下标：

• Parent(i) = floor(i/2)，i 的父节点下标
• Left(i) = 2i，i 的左子节点下标
• Right(i) = 2i + 1，i 的右子节点下标

上面的转换为层序遍历

Heapify堆化：

将数组列表转换为堆（也称为“堆化”它）

1. 把数列的数值视为完全二叉树的结点（从0开始）
2. 从倒数第二层开始，进行heapify，即父节点与子节点依次比较，把最大值交换到父节点
3. 以此类推，使这颗完全二叉树符合最大堆的性质

建堆规律：

1. 父节点的下标 = （i-1）/ 2    例：数值7的下标为3，其父节点的下标为（3-1）/2=1；
2. 左子节点的下标 = 2*i+1      例：数值2的下标为2，其左子节点的下标为  （2*2）+1=5；
3. 右子节点的下标= 2*i+2        例：数值2的下标为2，其左子节点的下标为  （2*2）+2=6；

二叉堆一般分为两种：最大堆和最小堆。

最大堆：

• 最大堆中的最大元素值出现在根结点（堆顶）
• 堆中每个父节点的元素值都大于等于其孩子结点（如果存在）

最大堆

最小堆：

• 最小堆中的最小元素值出现在根结点（堆顶）
• 堆中每个父节点的元素值都小于等于其孩子结点（如果存在）

最小堆

堆排序原理

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

• 最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
• 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
• 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

继续进行下面的讨论前，需要注意的一个问题是：数组都是 Zero-Based，这就意味着我们的堆数据结构模型要发生改变

Zero-Based

相应的，几个计算公式也要作出相应调整：

• Parent(i) = floor((i-1)/2)，i 的父节点下标
• Left(i) = 2i + 1，i 的左子节点下标
• Right(i) = 2(i + 1)，i 的右子节点下标
• 叶子节点的序号>=Math.floor(i/2)

最大堆调整（MAX‐HEAPIFY）的作用是保持最大堆的性质，是创建最大堆的核心子程序，作用过程如图所示：

Max-Heapify

由于一次调整后，堆仍然违反堆性质，所以需要递归的测试，使得整个堆都满足堆性质

下面来一个讲解的更加清楚的

1. 调整分支节点2（分支节点2不满足最大堆的性质）
   • 默认该分支节点为最大值
2. 将2与左右分支比较，从2，12，5中找出最大值，然后和2交换位置
   • 根据上面所将的二叉堆性质，分别得到分支节点2的左节点和右节点
   • 比较三个节点，得到最大值的下标max
   • 如果该节点本身就是最大值，则停止操作
   • 将max节点与父节点进行交换
3. 重复step2的操作，从2，4，7中找出最大值与2做交换
   • 递归

具体步骤：

• 找到所有分支节点：上面堆的性质提到过叶子节点的序号>=Math.floor(n/2)，因此小于Math.floor(n/2)序号的都是我们需要调整的节点。
  • 例如途中所示数组为[15,2,8,12,5,2,3,4,7] => Math.floor(9/2)=4 => index小于4的分别是[15,2,8,12](需要调整的节点)，而5，2，8，4，7为叶子节点。
• 将找到的节点都进行maxHeapify操作

用 JavaScript 可以表示如下：

/**
 * 从 index 开始检查并保持最大堆性质
 * @array
 * @index 检查的起始下标
 * @heapSize 堆大小
 **/
function maxHeapify(array, index, heapSize) {
  var iMax = index,
      iLeft = 2 * index + 1,
      iRight = 2 * (index + 1);
  if (iLeft < heapSize && array[index] < array[iLeft]) {
    iMax = iLeft;
  }
  if (iRight < heapSize && array[iMax] < array[iRight]) {
    iMax = iRight;
  }
  if (iMax != index) {
    swap(array, iMax, index);
    maxHeapify(array, iMax, heapSize); // 递归调整
  }
}
function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

最小堆调整

minHeapify (arr, i, length) {
    let min = i
    if (i >= length) {
        return
    }
    // 当前序号的左节点
    const l = i * 2 + 1
    // 当前需要的右节点
    const r = i * 2 + 2
    // 求当前节点与其左右节点三者中的最大值
    if (l < length && arr[l] < arr[min]) {
        min = l
    }
    if (r < length && arr[r] < arr[min]) {
        min = r
    }
    // 最终max节点是其本身,则已经满足最大堆性质，停止操作
    if (min === i) {
        return
    }
    // 父节点与最大值节点做交换
    swap(arr, i, min)
    // 递归向下继续执行
    this.maxHeapify(arr, min, length)
}

通常来说，递归主要用在分治法中，而这里并不需要分治。而且递归调用需要压栈/清栈，和迭代相比，性能上有略微的劣势。当然，按照20/80法则，这是可以忽略的。但是如果你觉得用递归会让自己心里过不去的话，也可以用迭代，比如下面这样：

• 创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，
• Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。
• 如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。

Build-Max-Heap流程如下：

用 JavaScript 描述如下：

function buildMaxHeap(array, heapSize) {
  var i,iParent = Math.floor((heapSize - 1) / 2); 
  for (i = iParent; i >= 0; i--) {
    maxHeapify(array, i, heapSize);
  }
}

堆排序（Heap-Sort）是堆排序的接口算法，

1. Heap-Sort先调用Build-Max-Heap将数组改造为最大堆，
2. 然后将堆顶和堆底元素交换，之后将底部上升，
3. 最后重新调用Max-Heapify保持最大堆性质。

由于堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分离出堆，重复n-1次之后，数组排列完毕。整个流程如下：

Heap-Sort

用 JavaScript 描述如下：

function heapSort(array, heapSize) {
  buildMaxHeap(array, heapSize);
  for (int i = heapSize - 1; i > 0; i--) {
    swap(array, 0, i);
    maxHeapify(array, 0, i);
  }  
}

JavaScript 语言实现

/**
 * @description 堆排序-层序遍历数据
 *  1、Heap-Sort先调用Build-Max-Heap将数组改造为最大堆，
 *  2、然后将堆顶和堆底元素交换，之后将底部上升，
 *  3、最后重新调用Max-Heapify保持最大堆性质。
 * @param arr {Array} 待排序数组
 * @return {*}
 */
function heapSort(arr) {
    if(arr.length>1){
        // 建立最大堆，堆顶(数组第一元素)就是最大元素
        debugger
        buildHeap(arr);
        // 然后将堆顶和堆底元素交换，最大元素在数组末尾，
        //    剩下的数组元素再重新建立最大堆，堆顶（数组第一元素）和数组倒数第i个元素交换，循环此步骤
        for(let i=arr.length-1;i>0;i--){
            swap(arr,0,i);
            adjustHeap(arr,0,i);
        }
    }
    return arr;
}

/**
 * @description 创建最大堆，把最大元素冒泡至堆顶
 * @param arr {Array}
 */
function buildHeap(arr) {
    // 叶子节点的序号>=Math.floor(n/2)，因此小于Math.floor(n/2)序号的都是我们需要调整的节点。
    for(let i=Math.floor(arr.length/2);i>=0;i--){
        adjustHeap(arr,i,arr.length);
    }
}

/**
 * 找到堆中最大元素，并调整至堆顶
 * @param arr
 * @param pos
 * @param len
 */
function adjustHeap(arr,pos,len) {
    // 子左结点
    let child=pos*2+1;
    while (child<len){
        // 如果子左结点 少于子右结点，直接比较子右结点
        if(child+1<len&&arr[child]<arr[child+1]){
            child++
        }
        // 如果子结点大于父节点，父子结点交互位置（子结点冒泡至父节点位置，层层冒泡变最大堆）
        if(arr[child]>arr[pos]){
            swap(arr,child,pos);
            pos=child;
            child=pos*2+1;
        }else {
            break;
        }
    }

}

/**
 * 待排序数组
 * @param arr {Array}
 * @param a {Number}
 * @param b {Number}
 */
function swap(arr,a,b) {
    let swap=arr[a];
    arr[a]=arr[b];
    arr[b]=swap;
}
let testArr=[4,3,21,1,4,100,9,1];
console.log(heapSort(testArr));

最后，把上面的整理为完整的 javascript 代码如下：

参考文章

• Wikipedia
• 维基百科，堆排序
• 维基百科，二叉树
• Algorithms Chapter 6 Heapsort
• Heap Sort
• 堆与堆排序
• 堆排序
• 堆排序(Heap Sort)算法学习
• Sorting Algorithm Animations
• https://godbasin.github.io/2017/07/23/heap-sort/
• 排序算法--堆排序--详解与代码实例https://blog.csdn.net/alzzw/article/details/98087519
• js数据结构-二叉树（二叉堆） https://segmentfault.com/a/1190000017761929

转载本站文章《再谈堆排序：堆排序算法流程步骤透解—最大堆构建原理》, 请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/8072.html