堆、并查集、哈希表.ppt

《算法艺术与信息学竞赛》标准课件 实用数据结构 刘汝佳 目录 一、堆 二、并查集 三、哈希表 一、堆 堆(heap)经常被用来实现优先队列(priority queue): 可以把元素加入到优先队列中, 也可以从队列中取出优先级最高的元素 Insert(T, x): 把x加入优先队列中 Delete(T, x): 获取优先级最高的元素x, 并把它从优先队列中删除 堆的操作 除了实现优先队列, 堆还有其他用途, 因此操作比优先队列多 Insert(T, x): 插入元素a Getmin(T, x): 获得并删除最小值 DecreaseKey(T, x, p): 把x的优先级降为p Build(T, x): 把数组x建立成最小堆 显然, 用堆很容易实现优先队列 堆的定义 堆是一个完全二叉树 所有叶子在同一层或者两个连续层 最后一层的结点占据尽量左的位置 堆性质 为空, 或者最小元素在根上 两棵子树也是堆 存储方式 最小堆的元素保存在heap[1..hs]内. 根在heap[1] K的左儿子是2k, K的右儿子是2k+1, K的父亲是[k/2] 删除元素 删除最小值 直接删除根 用最后一个元素代替根上元素 向下调整 向下调整 首先选取当前结点p的较大儿子. 如果比p大, 调整停止, 否则交换p和儿子, 继续调整 插入元素和向上调整 插入元素是先添加到末尾, 再向上调整 向上调整: 比较当前结点p和父亲, 如果父亲比p小，停止; 否则交换父亲和p, 继续调整 堆的建立 从下往上一层一层的进行向下调整 所有的叶子无需调整, 因此从hs/2开始 可用数学归纳法证明循环变量为i时, 第i+1, i+2, …n均为最大堆的根 时间复杂度分析 向上调整/向下调整 每层是常数级别, 共logn层, 因此O(logn) 插入/删除 只调用一次向上或向下调整, 因此都是O(logn) 建堆 高度为h的结点有n/2h+1个,总时间为 代码: 向上调整 p为当前结点. 向上调整中q是父亲; 向下调整中q是小儿子.先保存heap[p]以节省赋值 代码: 向下调整 操作的实现 二、并查集 并查集维护一些不相交集合S={S1, S2, …, Sr}, 每个集合Sr都有一个特殊元素rep[Si], 称为集合代表. 并查集支持三种操作 Make-Set(x): 加入一个集合{x}到S, 且rep[{x}] = x. 注意, x不能被包含在任何一个Si中, 因为S里任何两个集合应是不相交的 Union(x, y): 把x和y所在的两个不同集合合并. 相当于从S中删除Sx和Sy并加入SxUSy Find-Set(x): 返回x所在集合Sx的代表rep[Sx] 链结构 每个集合用双向链表表示, rep[Si]在链表首部 Make-Set(x): 显然是O(1)的 Find-Set(x): 需要不断往左移, 直到移动到首部. 最坏情况下是O(n)的 Union(x, y): 把Sy接在Sx的尾部, 代表仍是rep[Sx]. 为了查找链表尾部, 需要O(n) 增强型链结构 给每个结点增加一个指回rep的指针 Make-Set(x): 仍为常数 Find-Set(x): 降为常数(直接读rep) Union(x, y): 变得复杂: 需要把Sy里所有元素的rep指针设为rep[Sx]! 增强型链结构的合并 可以把x合并到y中，也可以把y合并在x中 技巧1: 小的合并到大的中 显然, 把小的合并到大的中, 这一次Union操作会比较节省时间, 更精确的分析? 用n, m, f分别表示Make-Set的次数, 总操作次数和Find-Set的次数, 则有 定理: 所有Union的总时间为O(nlogn) 推论: 所有时间为O(m + nlogn) 证明: 单独考虑每个元素x, 设所在集合为Sx, 则修改rep[x]时, Sx至少加倍. 由于Sx不超过n, 因此修改次数不超过log2n, 总nlogn 树结构 每个集合用一棵树表示, 根为集合代表 树结构的合并 和链结构类似, 小的合并到大的中 技巧2: 路径压缩 查找结束后顺便把父亲设置为根, 相当于有选择的设置rep指针而不像链结构中强制更新所有rep 路径压缩的分析 设w[x]为x的子树的结点数, 定义势能函数 Union(xi, xj)增加势能. 最多会让w[rep[xi]] 增加w[rep[xj]]=n, 因此势能增加不超过logn Find-Set(x)减少势能. 把路径压缩看作是从根到结点x的向下走过程, 则除了第一次外的其他向下走的步骤p?c会让c的子树从p的子树中移出, 即w[p]减少w[c], 而其他点的w值保持不变 路径压缩的分析 Find-Set除了第一次外的其他向下走的步骤