6-堆排序-算法导论
2016-05-31 22:28:01 9 举报AI智能生成
算法导论的第六章笔记
作者其他创作
大纲/内容
堆的定义
是一个数组，除了最底层外，该树是完全充满的，而且是从左向右填充
两个属性
A.length——数组元素的个数
A.heap-size——数组中存储的堆元素的个数
最大堆与最小堆
最大堆
除了根节点外的所有节点都要满足：当前节点值不大于其父节点值
最小堆
除了根节点外的所有节点都要满足：当前节点值不小于其父节点值
堆的高度 or 根节点的高度
即根节点的高度，亦即根节点到叶节点的最长简单路径上的边数
节点深度与高度区别
节点深度
从根节点到当前节点的层数
节点高度
从当前节点到最长简单路径叶节点层数
性质
维护堆
时间复杂度 O( lgn )
算法思路Max-Heapify(A,i)
输入(A,i)_数组A和节点i
对于 i以及 i.left, i.right,如果 i是最大的直接退出； 如果i不是最大的，那么 记录最大的那个元素下标为 largest，交换i与largest元素位置，并递归 （A, largest）
建堆
即将一个无序数组转化为最大堆
算法思路Build-Max-Heap(A)
令 i=[n/2]到1，并分别调用Max-Heapify(A,i)
时间复杂度O(n)
堆排序算法
思路
建立最大堆——>从 i=A.length to 2循环， 每次交换A[1]与A[i]——>维护堆（每次取出的A[1]排列起来即使有序结果）
堆的数组形式
以数组存储堆时，存储方式为：根左右根左右....——因为除了最底层节点外，堆的二叉树为完全二叉树，所以根左右是可行的
性质：含n个堆元素的数组中，叶节点下标分别为[n/2]+1,[n/2]+2,...
应用-优先队列
优先队列的操作
Insert(S,x)
功能：将元素x插入集合S中
Maxmum(S)
返回最大键值的元素
return A[1]
Heap-Extract-Max(A)
功能：去掉并返回A中的最大键值的元素
去掉A[1] 且堆尺寸减一，,并将A[A.heap-size ]放在A[1]处然后调用Max-Heapify(A,1)进行 维护堆的操作即可
Heap-Increase-Key(A,i,key)
功能：将i下标对应的关键字增加到key处（假定 key>A[i]）
A[i]=key——> while循环：交换 A[i]与 A[parent(i)] 然后 i= patent(i) %while循环end
Max-Heap-Insert(A,key)
功能：插入元素key
A尺寸加1——>A[ A.heap-size ] = -无穷——>调用Heap-Increase-Key(A, A.heap-size, key)
职业：暂无
0 条评论
下一页
