堆排序引入了另外一种算法设计技术:利用某种数据结构(在此算法中为“堆”)来管理算法执行中的信息。
一、堆
我们通常使用的堆的二叉堆,它是一种数组对象,可以被视为一棵完全二叉树。树中的每个节点与数组中的节点相对应。如下图所示:
表示堆的数组通常由两个属性:数组中元素的个数length[A],存放在A中的堆的元素的个数heap-size[A]。也就是说存放在A中的一些元素可能不属于对应的堆。因此:
heap-size[A] <= length[A]。
给定了某个节点的下标i,其父节点、左儿子以及右儿子可以很容易计算出来:
注意:下标均以1开始,而不是0
父节点:PARENT(i) = floor(i / 2)(向下取整)
左儿子:LEFT(i) = 2 * i
右儿子:RIGHT(i) = 2 * i + 1
堆的分类
二叉堆通常分为大根堆和小根堆。
在大根堆中,对于以某个节点为根的子树,其各节点的值都不大于其根节点的值,即A[PARENT(i)] >= A[i]
小根堆则正好相反。
在堆排序算法中,我们使用的是大根堆。小根堆通常在构造优先队列时使用。
堆的高度
节点在堆中的高度被定义为此节点到叶子的最长简单下降路径中边的数目。
堆的高度即根节点的高度。
二、堆的调整
很多时候,一棵二叉树不满足大根堆的性质,我们需要采用某种算法进行调整以使其变为大根堆。下面的函数MaxHeapify将会实现此功能。我们假定以某个节点i的左儿子节点和右儿子节点为根的子树都是大根堆,但是A[i]可能小于其子节点的值,这样就违背了大根堆的性质。
算法大致思想:
首先找出i节点和其左右子节点共3个节点中值最大的节点,如果不是i,则将i与值最大的节点互换。这样确保了根i处的值是最大的。然后调整以刚才与i互换的子节点为根的子树,递归调用算法MaxHeapify。
算法C++代码实现:
图示说明:
时间复杂度的分析:
调整A[i]、A[left]、A[right]的时间为常量时间。下面分析递归调整子树所需的时间。
假设树的节点个数为n,则i节点的子树节点个数最多为2n/3(在最底层刚好半满的时候),推导过程:
树总的节点个数
n = pow(2,0) + pow(2,1) + ... + pow(2,h - 1 - 1) + 1 / 2 *pow(2,h - 1),其中h为树的高度(根为第一层)
= 3 * pow(2,h - 2) - 1
假设根节点的左儿子所对应的子树节点数大于右子树的节点,其高度应为h - 1,节点数:
pow(2,0) + pow(2,1) + ... + pow(2,h - 1 - 1) = pow(2,h - 1) - 1
结合上面的式子可达到,子树的最大节点数为(2 * n - 1) / 3.
这样,调整堆的时间复杂度的推算为:
T(n) <= T(2n / 3) + O(1)
求解递归式得到:T(n) = O(lgn)。或者是O(h),h为树的高度。
三、建堆
我们可以自底向上地依次调整子树来获得大根堆。
注意:子数组A[floor(n/2) + 1]...A[n]是树的叶子。显然叶子可以看成只有一个元素的大根堆,不用调整。只需从非叶子节点自后向前依次调整即可。
C++代码实现:
一个有n个元素堆的高度为floor(lgn),并且在任意高度h上之多有ceil(n/pow(2,h+1))个节点。
这样,时间复杂度推算为:
即可以在线性时间内将一个无序数组建成大根堆。
4、堆排序
首先是将无序数组建成大根堆,然后通过把最大元素即根与A[n]互换使得最大元素到达正确位置。
然后将节点n从堆中去掉,原来根的子女仍然是大根堆,但是新的根元素可能违反了大根堆的规则,必须重新调整A[1,...,n - 1]为大根堆。这样重复进行。直至堆的大小变为1才结束。
C++代码实现:
图示说明:
堆排序的时间复杂度是O(nlgn)。而且是一种原地排序算法,即在任何时刻数组中只有常数个元素存储在输入数组以外。
程序实例:
运行结果:
分享到:
相关推荐
经典排序算法 - 堆排序Heap sort序 经典排序算法 - 地精排序Gnome Sort 经典排序算法 - 奇偶排序Odd-even sort 经典排序算法 - 梳排序Comb sort 经典排序算法 - 耐心排序Patience Sorting 经典排序算法 - 珠...
各种排序算法,包括希尔算法,快速排序,堆排序-A variety of sorting algorithms, including the Hill algorithm, quick sort, heap sort
到目前为止涵盖的算法: 名称功能名称快速排序quick_sort 气泡排序bubble_sort 选择排序selection_sort 插入排序insert_sort 堆排序heap_sort 合并排序merge_sort用法: 安装pip install -r requirements.txt 跑步...
如何让它自己工作-将源代码下载到src文件夹-通过创建新的reactjs应用并...使用ReactJS来提高对网站内用户界面设计,测试和调试的理解改进了数据结构和算法的概念以及前端端开发 堆排序合并排序快速排序气泡排序前:后:
经典数据结构和算法库这个项目需要c++11 该库旨在为程序员提供...职能插入排序选择排序冒泡排序MergeSort(未就地) 合并排序合并快速排序快速排序分区 堆在Heap.h 中, namespace Structure等。 班级堆基础最佳尺寸
void Heap_Sort(SqList &L) // 堆排序 { int i; for (i=L.length/2; i>0; i--)// build the heap { Heap_Adjust(L,i,L.length); } for (i=L.length; i>1; i--) { L.r[0]=L.r[i];// 将 堆顶记录和当前未经...
示例 - 自行运行堆排序演示: $ ruby -r ./heap_sort_demo.rb -e " simple_test " [10, 23, 25, 30, 37] 示例 - 在自定义长度的随机数组上运行堆排序演示: $ ruby -r ./heap_sort_demo.rb -e " puts heap_sort...
算法清单所有程序都分为1级到4级(最简单的是1级)排序:实现气泡排序| O(n ^ 2)| 2级:实现选择排序| O(n ^ 2)| 2级:实现插入排序| O(n ^ 2)| 2级:构建最大堆并按升序对数组进行排序| 3级 :构建最大堆并以...
# 如果某个内部heap(堆积)表大小超过tmp_table_size,MySQL可以根据需要自动将内存中的heap表改为基于硬盘的MyISAM表。还可以通过设置tmp_table_size选项来增加临时表的大小。也就是说,如果调高该值,MySQL同时将...
F:排序 G:矩阵 H:散列 I:字符串 J:链接列表 K:堆叠 L:排队 M:出队 N:树 O:二进制搜索树 P:堆 问:图 R:贪婪 S:回溯 T:动态编程 U:特里 V:细分树 W:不相交集 gh,不是另一个DSA存储库,反正还是。 ...