找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法:堆排序

admin 2019-8-11 11:59 80人围观 C++相关

什么是排序?
考虑对于给定输入的某一个数组

, 经过排序算法,我们可以得到原始排列的一个序列

, 其中

.

什么是堆?
堆,又称为二叉堆,它可以被看为一个完全二叉树,但实际上是由数组存储的数据结构。

存储堆的数组 A 有属性有两个:1. heap_size, 表示堆中存在多少元素;2.  A.size, 表示数组元素的个数。即A[1,…, A,size()] 可能都存储数据,但是只有 A[1,…, heap_size] 中的数据为堆得有效数据(方便删除标记)。这里有

.

这里需要注意的是,为了表示方便,数组下标从 1 开始,A[0] 可以作为哨兵元素存在,但不统计在内。

对于二叉树的形式,给定一个结点的下标

, 我们给出它的父亲下标为

, 左孩子下标为

, 右孩子下标为

.

图例:




二叉堆可以分为两种:1. 最大堆:除了根节点之外,所有结点的关键值都要小于父亲结点的关键值;2. 最小堆:除了根节点之外,所有结点的关键值都要大于父亲结点的关键值。
上例所示的堆为最大堆。

高度:由于堆可以视为二叉树的形式,因此堆的高度定义为根结点到叶结点最长简单路径上的边的数目。一个包含 n 个结点的堆的高度为

.

堆的操作(以最大堆为例):1. max_heapify; 2. build_max_heap; 3. heap_sort; 4. max_heap_insert, heap_extract_max, heap_increase_key, heap_maximum.


max_heapify: 用于维护最大堆的性质。
输入为一个数组 A, 一个下标 i, 在调用 max_heapify 时,我们确定 i 的左孩子和右孩子都已经是最大堆,此时,若

,则违背了最大堆的性质,max_heapify 通过让A[i] 在最大堆中的高度逐级下降,从而维护最大堆的性质。

为了让操作更加直观,进行以下演示:输入为 A =  [16, 4, 10, 14, 7, 9, 3 , 2, 8, 1] , i = 2 处A[i] = 4, 违背了最大堆的性质:




max_heapify 的代码为:
vector<int> A = {-1, 27,17,3,16,13,10,1,5,7,12,4,8,9,0}; //A[0]作为哨兵
int heap_size = A.size() - 1;   //因为多了一个 A[0], 所以要减去1.

void max_heapify( vector<int>& A, int i){
    int L = 2 * i, R = 2 * i + 1;

    int large_index = i;
    if( L <= heap_size && A[i] < A[L])
        large_index = L;
    if( R <= heap_size && A[large_index] < A[R])
        large_index = R;

    if( large_index != i){
        swap( A[large_index], A[i]);
        max_heapify( A, large_index);
    }
}

测试:




算法分析:容易得到 max_heapify 的时间复杂度为

, 即树的高度。


build_max_heap: 建堆操作,利用max_heapify 可以把一个大小为 n = A.size() 的数组自底向上建堆。
注意,对于A[ n>>1 + 1, …, n] 中元素为叶节点,它们可以视为只有一个元素的最大堆,此时不需要对它们进行维护堆的性质,只需要对下标为 1, …, n>>1 调用一次 max_heapify 即可。

为了让操作更加直观,进行以下演示:输入为 A = [4, 1,3,2,16,9,10,14,8,7] , 对其进行 build_max_heap 操作。



代码:vector<int> A = {-1, 5, 3, 17, 10, 84, 19, 6, 22, 9}; //A[0]作为哨兵
int heap_size = A.size() - 1;   //因为多了一个 A[0], 所以要减去1.

void max_heapify( vector<int>& A, int i){
    int L = 2 * i, R = 2 * i + 1;

    int large_index = i;
    if( L <= heap_size && A[i] < A[L])
        large_index = L;
    if( R <= heap_size && A[large_index] < A[R])
        large_index = R;

    if( large_index != i){
        swap( A[large_index], A[i]);
        max_heapify( A, large_index);
    }
}

测试用例:




算法分析:从直观上来看,每次调用 max_heapify 的时间复杂度为

, 调用了

次,该算法时间复杂度为

, 但是,由于不同结点的树高不同,假设每个结点的树高为 h, 则build_max_heap的时间复杂度为:



其中,

的意义是n个元素的堆中,至多有

个高度为 h 的点。
另外,由

可得



注意,改方法建堆的时间复杂度为线性时间,但若使用插入的方法建堆,时间复杂度为

.
插入的方法建堆是自顶向下,逐个插入。


heap_sort: 即堆排序。利用 build_max_heap 将数组 A 建成最大堆,此时,最大元素总在根节点处(A[1]), 可让 A[1] 与 A[heap_size] 互换,然后取出最后一个节点,同时heap_size--, 再将交换后的A[1]移动到满足最大堆性质的位置,重复以上步骤。

为了让操作更加直观,进行以下演示:输入最大堆 A = [16,14,10,8,7,9,3,2,4,1] , 对其进行 heap_sort 操作。




其代码如下:
vector<int> A = {-1, 5, 13, 2,25,7,17,20,8,4}; //A[0]作为哨兵
int heap_size = A.size() - 1;   //因为多了一个 A[0], 所以要减去1.

void max_heapify( vector<int>& A, int i){
    int L = 2 * i, R = 2 * i + 1;

    int large_index = i;
    if( L <= heap_size && A[i] < A[L])
        large_index = L;
    if( R <= heap_size && A[large_index] < A[R])
        large_index = R;

    if( large_index != i){
        swap( A[large_index], A[i]);
        max_heapify( A, large_index);
    }
}

void build_max_heap( vector<int>& A){
    for( int i = (A.size() - 1) >> 1; i > 0; i--)//必须自底向上,否则不满足循环不变式
        max_heapify( A, i);
}

void heap_sort( vector<int>& A){
    //建成最大堆
    build_max_heap(A);
    for( int i = A.size() - 1; i > 1; i--){
        swap( A[i], A[1]);
        heap_size--;
        max_heapify(A, 1);
    }

}

测试:




算法分析:堆排序的时间复杂度为

.


----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:Coder的自我修养,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......