文档介绍：第4章堆和不相交集数据结构
上海第二工业大学温敬和
******@it.
2008年4月4日
1
引言(堆、不相交集)
堆
堆上的运算
创建堆
堆排序
最大堆和最小堆
不相交集数据结构
按秩合并措施
Union-Find算法
路径压缩
Union-Find算法的分析(略)
2
堆
㈠堆的引入
在许多算法中,需要支持下面二种运算:
插入元素
寻找最大值元素(或最小值元素)
支持这二种运算的数据结构称为优先队列。
可采用下述三种方法实现优先队列:
使用普通队列(或数组),插入容易(尾部),但寻找最大值需搜索整个队列,开销比较大。
使用排序数组,寻找最大值元素容易,插入操作需移动很多元素。
使用堆,寻找最大值元素容易,插入操作仅需移动少量元素。
3
(Page 74)
一个(二叉)堆是一棵几乎完全的二叉树,它的每个结点都满足堆的特性:设v是一个结点,p(v)是v的父结点,那么存储在p(v)中的数据项键值大于或等于存储在v中的数据项键值。
㈡堆的定义(二叉堆)
几乎完全二叉树(Page 71)
如果一棵二叉树,(在底层)除了最右边位置上的一个或几个叶子可能缺少外,它是丰满的,我们定义它为几乎完全二叉树。
①
②③
④⑤⑥⑦
⑧⑨⑩
4
堆数据结构支持下列运算
DeleteMax[H]:从一个非空堆H中,删除最大键值的数据项,并返回该数据;
Insert[H,x]:将数据项x插入堆H中;
Delete[H,i]:从堆中删除第i项;
MakeHeap[A]:将数组转换为堆。
堆的蕴含特性:
沿着每条从根到叶子的路径,元素的键值以降序(或称非升序)排列。
5
㈢堆的表示
有n个结点堆T,可以用一个数组H[1..n]用下面方式来表示:
T的根结点存储在H[1]中;
设T的结点存储在H[j]中,如果它有左子结点,则这个左子结点存储在H[2j]中;如果它还有右子结点,这个右子结点存储在H[2j+1];
若元素H[j]不是根结点,它的父结点存储在H[j/2]中。
由“几乎完全二叉树”的定义可知,如果堆中某结点有右子结点,则它一定也有左子结点。
堆具有如下性质:
key(H[j/2])≥key(H[j]) 2≤j≤n
6
201
172 93
104 115 46 57
38 79 510
㈣堆和它的数组表示法
把存储在堆中的数据项视为键值。按树的结点“自顶向下”、“从左至右”、“按1到n”的顺序进行编号,那么数组元素H[i]对应树中编号为i的结点。
20
17
9
10
11
4
5
3
7
5
1
2
3
4
5
6
7
8
9
10
H[2]=17的左子结点为H[2*2]=H[4]=10
H[2]=17的右子结点为H[2*2+1]=H[5]=11
H[9]=7的父结点为H[ 9/2]=H[4]=10
沿着每条从根到叶子的路径,元素的键值以降序排列。
7
堆上的运算
㈠ShiftUp
假定对于某个i>1,H[i]的键值变成大于它父结点的键值,这样违反了堆的特性,需使用称为ShiftUp的运算来修复堆。
ShiftUp运算沿着从H[i]到根结点的惟一路径,把H[i]移到适合它的位置上。在移动的每一步中,将H[i]的键值与它的父结点H[i/2]的键值相比较,若
若H[i] > H[i/2],则H[i]和H[i/2]互换(上移),继续。
若H[i]≤H[i/2] 或 i=1,终止。
8
②H[5]=25和H[2]=17互换,H[5]=17, H[2]=25。
①H[10]=25和H[5]=11互换,H[10]=11, H[5]=25。
201
172 9
10 115 4 5
3 7 510→25
例,H[10]的键值由5变为25。
20
17
9
10
11
4
5
3
7
25
1
2
3
4
5
6
7
8
9
10
③H[2]=25和H[1]=20互换,H[2]=20, H[1]=25。
25
20
9
10
17
4
5
3
7
11
20
17
9
10
25
4
5
3
7
11
20
25
9
10
17
4
5
3
7
11
9
过程 ShiftUp(参见Page 75)
输入:数组H[1..n]和索引i(1≤i≤n)
输出:上移H[i](如果需要),使它不大于父结点。
0. procedure ShiftUp(H[1.