< 排序大全系列 > 堆排序总结：

直观动图理解：

堆排序

算法知识导引：

1. 什么是 “堆” ？：

   堆是一种近似完全二叉树的结构，通常堆是通过 一维数组 来实现的。

   二叉树我们在学离散数学的时候都见过，那具体什么是 完全二叉树 呢？这个二叉树应该满足一下两个条件：

   1. 假设整个二叉树深度为 n，那么除了第 n 层及其树叶，其他各层的结点都达到了最大个数，有 2 个分叉
   2. 且第 n 层的树叶全部集中在左侧

从上到下以从大到小的关系形成的树可以叫做 最大堆，反之就叫做 最小堆。

注意：以最大堆为例并不代表层数更高，数字就一定更大，二叉堆只需要满足父结点比子结点大就可以了。

完全二叉树如下图所示：

完全二叉树图示

2. 那为什么可以用一维数组来表示，而不是单独写一个 完全二叉树类呢？：

   是因为完全二叉树有一些独特的性质：

   就如上图所示，我们的圈圈里现在还没有装数据，现在圈里的数字是序号。像这样从上到下，从左到右地依次给完全二叉树编号后，我们就可以根据 编号与结点 之间的微妙关系得出一些结论：

   1. n 号结点的下属左结点的序号是 2n
   2. n 号结点的下属右结点的序号是 2n+1
   3. 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;
   }
   

3. 那么一个二叉堆需要包含什么操作呢？：

   当有一个新的元素需要填入的时候，我们需要 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;
       }
   

那么接下来，我们就要正式开始实现 堆排序 了：我们给出了两种实现：

1. 第一种是将 所需要排序的 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();
       }
   }
   

2. 第二种，是在构造函数层面完成的，将 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 )。

值得改进的地方 —— 原地堆排序

我们上面的两个算法都有一个问题，那就是都需要新开辟一个数组，然后有序地填入值来形成一个有序数组。

可是这样的算法显然是不够好的，能不能就在原地空间内，将数据整合有序呢？

思路是这样的：

1. 通过刚才新的 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的相对次序。

参考资料：

1. https://www.bilibili.com/video/av23849333/?p=1

   数据结构与算法之堆(完整版) （主要是 p1 和 p6 ）Blibili uploader：Python空间

2. https://www.cnblogs.com/eniac12/p/5329396.html#s4

   CSDN精品博客文章：常用排序算法总结(一) Posted on 2016-03-28 22:13