堆排序总结

堆排序总结

直观动图理解:

堆排序


算法知识导引:

  1. 什么是 “堆” ?

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

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

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

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

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

    完全二叉树如下图所示:

完全二叉树表示

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

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

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

    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;
    }
    
  2. 那么一个二叉堆需要包含什么操作呢?

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

    数据结构与算法之堆(完整版) (主要是 p1p6 )Blibili uploader:Python空间

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

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

# 算法 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×