< 排序大全系列 > 堆排序总结：
直观动图理解：
堆排序
算法知识导引：
-
什么是 “堆” ？：
堆是一种近似完全二叉树的结构，通常堆是通过 一维数组 来实现的。
二叉树我们在学离散数学的时候都见过，那具体什么是 完全二叉树 呢？这个二叉树应该满足一下两个条件：
- 假设整个二叉树深度为 n，那么除了第 n 层及其树叶，其他各层的结点都达到了最大个数，有 2 个分叉
- 且第 n 层的树叶全部集中在左侧
从上到下以从大到小的关系形成的树可以叫做 最大堆，反之就叫做 最小堆。
注意：以最大堆为例并不代表层数更高，数字就一定更大，二叉堆只需要满足父结点比子结点大就可以了。
完全二叉树如下图所示：
完全二叉树图示
-
那为什么可以用一维数组来表示，而不是单独写一个 完全二叉树类呢？：
是因为完全二叉树有一些独特的性质：
就如上图所示，我们的圈圈里现在还没有装数据，现在圈里的数字是序号。像这样从上到下，从左到右地依次给完全二叉树编号后，我们就可以根据 编号与结点 之间的微妙关系得出一些结论：
- n 号结点的下属左结点的序号是 2n
- n 号结点的下属右结点的序号是 2n+1
- n 号结点（只要它有父结点）的父结点序号为 n/2 ，注意是计算机的整数除法
我们通常从一个数组的 [ 1 ] 位置开始填入值而不是 [ 0 ]。
接下来我们以最大堆为例，做一个 C++ 的代码实现：
#include <iostream> #include <algorithm> #include <cmath> #include <ctime> using namespace std; template<typename Item> class MaxHeap{ private: Item *data = NULL; int count; /* 有多少个有效的值 */ public: MaxHeap(int capacity){ /* capacity 容量 */ data = new Item[ capacity+1 ]; /* +1 是因为是从 [1] 开始存放的，浪费了一个小格间，要满足原有那么多数据的需求，就得 +1 */ } ~MaxHeap(){ delete [] data; /* 析构函数里，完成空间的清理 */ } int size(){ return count; } bool isEmpty(){ return count == 0; } } int main(){ MaxHeap<int> maxheap = MaxHeap<int>(100); /* 一定记得这里填入的 100 代表的是空间大小！*/ cout<< maxheap.size() << endl; return 0; } -
那么一个二叉堆需要包含什么操作呢？：
当有一个新的元素需要填入的时候，我们需要 SHIFT UP 操作：
private: void shiftUp( int k ){ while( k > 1 && data[k/2] < data[k] ){ /* k = 1 时就是根结点了，已经没有父结点可以判断了。*/ /* 第二个判断是 比较父结点是否小于子结点，如果是，那么就把大的向上推，小的换下来。*/ swap( data[k/2], data[k]); /* swap()大家都会写，就不再赘述 */ k /= 2; } } /* 之所以把 shiftUp 写成是 private ，是因为用户没有必要调用该函数。*/ public: void insert( Item item ){ data[count+1] = item; /* 在数组末尾，添加进新的一个元素*/ ++ count; }当我们需要取出一个元素的时候，我们必须要保证取出后，堆依然满足自身需要的那些条件，所以需要 SHIFT DOWN 操作：
/* 格式基本同上：*/ private: void shitDown(){ while( 2*k <= count ){ int j = 2*k; // 在此轮循环中，data[k] 和 data[j]交换位置 if( j+1 <= count && data[j+1] > data[j]) j += 1; if( data[k] >= data[j] ){ break; } swap( data[k], data[j] ); k = j; } } public: Item extractMax(){ assert( count > 0 ); Item ret = data[1]; /* 把此时的顶部元素保存下来 作为返回值*/ swap( data[1] , data[count] ); count --; shiftDown(1); /* 用最末的元素来 shiftDown 一遍整个二叉堆，达到维护的效果。*/ return ret; }
那么接下来，我们就要正式开始实现 堆排序 了：我们给出了两种实现：
-
第一种是将 所需要排序的 arr[] 数组的元素 通过 insert() 函数一个一个填入堆中：
代码如下：
template<typename> void heapSort(T arr[], int n){ MaxHeap<T> maxheap = MaxHeap<T>(n); for( int i =0; i<n ; i ++){ maxheap.insert(arr[i]); } for( int i = n-1; i>=0 ; i--){ /* 这里展示的是 从小到大的顺序，当然如果想改为从大到小的话，本来每次 extractMax() 就是取出最大值，那么改为 初始化 i = 0 就好了*/ arr[i] = maxheap.extractMax(); } } -
第二种，是在构造函数层面完成的，将 arr[] 数组传入 MaxHeap 类中
代码如下：
首先先需要在原 MaxHeap 类内添加一个新的构造函数： public: MaxHeap(Item arr[], int n){ data = new Item[ n+1 ]; capacity = n; for( int i=0; i<n ; i++ ) data[i+1] = arr[i]; count = n; for( int i = count/2 ; i>=1 ; i-- ){ shiftDown(i); } }我们是从最后一个叶子节点开始进行 shiftDown 操作，而在实际情况中，其实真正移动了的元素并不多，这样大大提高了效率，比一个一个地插入要好很多。
template<typename> void heapifySort(T arr[], int n){ MaxHeap<T> maxheap = MaxHeap<T>(arr, n); for( int i = n-1; i>=0 ; i--){ arr[i] = maxheap.extractMax(); } }
下面我们来看看经过测试后的结果：
Test For Radom Array, size = 1000000, radom range [0, 1000000]:
heapSort Time: 0.616283s
heapify Time: 0.573522s
--------------------------------
Test For Radom Nearly Ordered Array, size = 1000000, radom range [0, 1000000]:
heapSort Time: 0.620693s
heapify Time: 0.341337s
--------------------------------
Test For Radom Array, size = 1000000, radom range [0, 10]:
heapSort Time: 0.361128s
heapify Time: 0.322639s
--------------------------------
Heapify 的算法复杂度比较：
将n个元素逐个插入到一个空堆中，算法复杂度是 O( nlogn )，
heapifySort 的过程，算法复杂度是 O( n )。
值得改进的地方 —— 原地堆排序
我们上面的两个算法都有一个问题，那就是都需要新开辟一个数组，然后有序地填入值来形成一个有序数组。
可是这样的算法显然是不够好的，能不能就在原地空间内，将数据整合有序呢？
思路是这样的：
-
通过刚才新的 MaxHeap 的构造函数，可以让一个数组成为一个最大堆，那么假如有一个 max 指针，指向的一定是该数组的第一项。
Step 1
此时我们把它移到最末尾，那么此时 上图中的 v 找到了最合适的位置，因为它是最大值，所以放在了最末尾。
Step 2
但此时，w已经不是最大值，前面从 [ 0 ] 到 倒数第二个 元素之间，就不再是一个最大堆 Max Heap 了。所以我们对 w 执行一次 shiftDown 操作，使得橙色部分重新成为一个 最大堆。
Step 3
那么第一个元素又是该最大堆中相对的最大值了，所以继续甩到末尾排列。
Step 4
如此递归往复，就可以在原有数组内，完成原地的堆排序。
各项指标：
分类 -------------- 内部比较排序
数据结构 ---------- 数组
最差时间复杂度 ---- O(nlogn)
最优时间复杂度 ---- O(nlogn)
平均时间复杂度 ---- O(nlogn)
所需辅助空间 ------ O(1)
稳定性 ------------ 不稳定
堆排序是不稳定的排序算法，不稳定发生在堆顶元素与A[i]交换的时刻。
比如序列：{ 9, 5, 7, 5 }，堆顶元素是9，堆排序下一步将9和第二个5进行交换，得到序列 { 5, 5, 7, 9 }，再进行堆调整得到{ 7, 5, 5, 9 }，重复之前的操作最后得到{ 5, 5, 7, 9 }从而改变了两个5的相对次序。
参考资料：
-
https://www.bilibili.com/video/av23849333/?p=1
数据结构与算法之堆(完整版) （主要是 p1 和 p6 ）Blibili uploader：Python空间
-
https://www.cnblogs.com/eniac12/p/5329396.html#s4
CSDN精品博客文章：常用排序算法总结(一) Posted on 2016-03-28 22:13
网友评论