第4章 堆和不相交数据结构VIP免费

第第44章堆和不相交集数据章堆和不相交集数据结构结构4.14.1引言（堆、不相交集）引言（堆、不相交集）4.2堆4.2.1堆上的运算4.2.2创建堆4.2.3堆排序4.2.4最大堆和最小堆4.3不相交集数据结构4.3.1按秩合并措施4.3.3Union-FindUnion-Find算法算法4.3.2路径压缩4.3.44.3.4Union-FindUnion-Find算法的分析（略）算法的分析（略）4.24.2堆堆㈠堆的引入㈠堆的引入在许多算法中，需要支持下面二种运算：在许多算法中，需要支持下面二种运算：插入元素插入元素寻找最大值元素（或最小值元素）寻找最大值元素（或最小值元素）支持这二种运算的数据结构称为优先队列。支持这二种运算的数据结构称为优先队列。可采用下述三种方法实现优先队列：可采用下述三种方法实现优先队列：①①使用普通队列（或数组），插入容易（尾部），使用普通队列（或数组），插入容易（尾部），但寻找最大值需搜索整个队列，开销比较大。但寻找最大值需搜索整个队列，开销比较大。②②使用排序数组，寻找最大值元素容易，插入操作使用排序数组，寻找最大值元素容易，插入操作需移动很多元素。需移动很多元素。③③使用堆，寻找最大值元素容易，插入操作仅需移使用堆，寻找最大值元素容易，插入操作仅需移动少量元素。动少量元素。定义定义4.14.1（（Page74Page74））一个（二叉）堆是一棵几乎完全的二叉树，一个（二叉）堆是一棵几乎完全的二叉树，它的每个结点都满足堆的特性：设它的每个结点都满足堆的特性：设vv是一个结点，是一个结点，p(v)p(v)是是vv的父结点，那么存储在的父结点，那么存储在p(v)p(v)中的数据中的数据项键值大于或等于存储在项键值大于或等于存储在vv中的数据项键值。中的数据项键值。㈡堆的定义（二叉堆）㈡堆的定义（二叉堆）几乎完全二叉树（几乎完全二叉树（Page71Page71））如果一棵二叉树，（在底如果一棵二叉树，（在底层）除了层）除了最右边最右边位置上的一个或位置上的一个或几个几个叶子叶子可能缺少外，它是丰满可能缺少外，它是丰满的，我们定义它为几乎完全二叉的，我们定义它为几乎完全二叉树。树。①①②②③③④④⑤⑤⑥⑥⑦⑦⑧⑨⑩⑧⑨⑩堆数据结构支持下列运算堆数据结构支持下列运算DeleteMax[H]DeleteMax[H]：从一个非空堆：从一个非空堆HH中，删中，删除最大键值的数据项，并返回该数据；除最大键值的数据项，并返回该数据；Insert[H,x]Insert[H,x]：将数据项：将数据项xx插入堆插入堆HH中；中；Delete[H,i]Delete[H,i]：从堆中删除第：从堆中删除第ii项；项；MakeHeap[A]MakeHeap[A]：将数组转换为堆。：将数组转换为堆。堆的蕴含特性：堆的蕴含特性：沿着每条从根到叶子的路径，元素的键值以沿着每条从根到叶子的路径，元素的键值以降序（或称非升序）排列。降序（或称非升序）排列。㈢堆的表示㈢堆的表示有有nn个结点堆个结点堆TT，可以用一个数组，可以用一个数组H[1..n]H[1..n]用下面用下面方式来表示：方式来表示：TT的根结点存储在的根结点存储在H[1]H[1]中；中；设设TT的结点存储在的结点存储在H[j]H[j]中，如果它有左子结点，中，如果它有左子结点，则这个左子结点存储在则这个左子结点存储在H[2j]H[2j]中；如果它还有右子结中；如果它还有右子结点，这个右子结点存储在点，这个右子结点存储在H[2j+1]H[2j+1]；；若元素若元素H[j]H[j]不是根结点，它的父结点存储在不是根结点，它的父结点存储在H[H[j/2j/2]]中。中。由“几乎完全二叉树”的定义可知，如果堆中某由“几乎完全二叉树”的定义可知，如果堆中某结点有右子结点，则它一定也有左子结点。结点有右子结点，则它一定也有左子结点。堆具有如下性质：堆具有如下性质：key(H[key(H[j/2j/2])≥key(H[j])])≥key(H[j])2≤j≤n2≤j≤n20201117172299331010441111554466557733887799551010㈣堆和它的数组表示法㈣堆和它的数组表示法把存储在堆中的数据项视为键值。按树的结点把存储在堆中的数据项视为键值。按树的结点““自顶向下自顶向下”、“”、“从左至右从左至右”、“”、“按按11到到nn””的顺序的顺序进行编号，那么数组元素进行编号，那么数组元素H[i]H[i]...