6-堆排序-算法导论

算法导论-堆排序

堆的定义

是一个数组，除了最底层外，该树是完全充满的，而且是从左向右填充

两个属性

A.length——数组元素的个数

A.heap-size——数组中存储的堆元素的个数

最大堆与最小堆

最大堆

除了根节点外的所有节点都要满足：当前节点值不大于其父节点值

最小堆

除了根节点外的所有节点都要满足：当前节点值不小于其父节点值

堆的高度 or 根节点的高度

即根节点的高度，亦即根节点到叶节点的最长简单路径上的边数

节点深度与高度区别

节点深度

从根节点到当前节点的层数

节点高度

从当前节点到最长简单路径叶节点层数

性质

维护堆

时间复杂度 O( lgn )

建堆

即将一个无序数组转化为最大堆

算法思路Build-Max-Heap(A)

时间复杂度O(n)

堆排序算法

思路

建立最大堆——从 i=A.length to 2循环， 每次交换A[1]与A[i]——维护堆（每次取出的A[1]排列起来即使有序结果）

堆的数组形式

以数组存储堆时，存储方式为：根左右根左右....——因为除了最底层节点外，堆的二叉树为完全二叉树，所以根左右是可行的

应用-优先队列

优先队列的操作

功能：将元素x插入集合S中

Maxmum(S)

返回最大键值的元素

return A[1]

Heap-Extract-Max(A)

功能：去掉并返回A中的最大键值的元素

功能：将i下标对应的关键字增加到key处（假定 keyA[i]）

A[i]=key—— while循环：交换 A[i]与 A[parent(i)] 然后 i= patent(i) %while循环end

功能：插入元素key