二叉堆、并查集和树状数组
优先队列
• 优先队列(priority queue): 可以把元素加入到优先队列中, 也可以从队列中取出
优先级最高的元素, 即以下ADT
– Insert(T, x): 把x加入优先队列中
– DeleteMin(T, x): 获取优先级最高的元素x, 并把它从优先队列中删除堆的操
作
• 用二叉堆(binary heap)很容易实现优先队列
• 除了实现优先队列, 堆还有其他用途, 因此操作比优先队列多
– Getmin(T, x): 获得最小值
– Delete(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]
删除最小值元素
• 三步法
– 直接删除根
– 用最后一个元素代替根上元素
– 向下调整
1
评论0