数据结构与算法系列之一：八大排序之堆排序

本文主要是介绍数据结构与算法系列之一：八大排序之堆排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

转载请注明作者和出处：http://blog.csdn.net/u011475210
个人博客：https://wordzzzz.github.io/ && https://wordzzzz.gitee.io/
代码地址：https://github.com/WordZzzz/Note/tree/master/DS-A
博客作者：WordZzzz，一只热爱技术的文艺青年

- 堆排序
  - 前言
  - 简介
  - 步骤
  - 演示
  - 代码
    - 递归版
    - 迭代版
  - 算法复杂度
  - 分析

堆排序

前言

建议先看排序综述，传送门：数据结构与算法系列之一：八大排序综述。

简介

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

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：

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

在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：

最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点。
创建最大堆（Build_Max_Heap）：将堆所有数据重新排序。
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

步骤

基于以上堆相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用del_max()函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。真正的原地堆排序使用了另外一个小技巧。堆排序的过程是：

创建一个堆 $H[0..n-1]$ 。
把堆首（最大值）和堆尾互换。
把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置。
重复步骤2，直到堆的尺寸为1。

演示

wikipedia的大数据规模演示：

代码

递归版

/*
* 堆排序递归版
*/template <typename T>
void MaxHeapifyRecursive(T *array, int i, int heapSize) {int sonl = 2 * i + 1;int sonr = 2 * i + 2;int dad = i;if (sonl <= heapSize && array[sonl]>array[i]){                  //如果左子结点大于父结点，则父结点指向子结点dad = sonl;}if (sonr <= heapSize && array[sonr]>array[dad]){                //如果右子结点大于父结点，则父结点指向子结点dad = sonr;}if (dad != i){                                                  //如果dad != i则说明父结点不是最大值，交换后递归执行MaxHeapifyRecursiveswap(array[i], array[dad]);MaxHeapifyRecursive(array, dad, heapSize);}
}template <typename T>
void HeapSort(T *array, const int length) {if (array == NULL)throw invalid_argument("Array must not be empty");if (length <= 0)return;//初始化，i从最后一个父结点开始调整for (int i = length / 2 - 1; i >= 0; --i){//构建最大堆 MaxHeapifyRecursive(array, i, length - 1);
//      MaxHeapifyIteration(array, i, length - 1);}//先将第一个元素和已经排好的元素前一位做交换，再从新调整（刚调整的元素之前的元素），直到排序完毕for (int i = length - 1; i >= 0; --i){swap(array[0], array[i]);MaxHeapifyRecursive(array, 0, i - 1);
//      MaxHeapifyIteration(array, 0, i - 1);}
}

迭代版

/*
* 堆排序迭代版
*/template <typename T>
void MaxHeapifyIteration(T *array, int left, int right) {//建立父结点指针和子结点指针int dad = left;int son = dad * 2 + 1;while (son <= right) {                                          //若子结点指针在范围内才做比较if (son + 1 <= right && array[son] < array[son + 1])        //先比较两个子结点的大小，选择最大的son++;if (array[dad] > array[son])                                //如果父结点大于子结点代表调整完毕，直接跳出循环return;else {                                                      //否则交换父子内容在继续子结点和孙结点的比较swap(array[dad], array[son]);dad = son;son = dad * 2 + 1;}}
}template <typename T>
void HeapSort(T *array, const int length) {if (array == NULL)throw invalid_argument("Array must not be empty");if (length <= 0)return;//初始化，i从最后一个父结点开始调整for (int i = length / 2 - 1; i >= 0; --i){//构建最大堆 
//      MaxHeapifyRecursive(array, i, length - 1);MaxHeapifyIteration(array, i, length - 1);}//先将第一个元素和已经排好的元素前一位做交换，再从新调整（刚调整的元素之前的元素），直到排序完毕for (int i = length - 1; i >= 0; --i){swap(array[0], array[i]);
//      MaxHeapifyRecursive(array, 0, i - 1);MaxHeapifyIteration(array, 0, i - 1);}
}

算法复杂度

数据结构数组
最坏时间复杂度 $O(n\log n)$
最优时间复杂度 $O(n\log n)$
平均时间复杂度 $O(n\log n)$
空间复杂度 $O(n)$ total, $O(1)$ auxiliary

分析

原地堆排序已经是空间优化版本了，因为它不再需要申请额外的空间。

整个算法的过程分为建堆和排序两个过程，首先对现有数组建立最大堆，然后一边提取堆顶的最大值，一边减小堆的尺寸，最后堆尺寸为1时，排序也就完成了。如果大家对整个算法的执行过程不太了解，可以看一下下面这两张图，第一张是建堆的过程示意图，第二张是排序的过程示意图。图片来自：http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/