二叉堆并查集

Written with StackEdit.

二叉堆

完全二叉树优先从左边开始填充empty或最小元素在根上子树也是堆

储存方式

一维数组 从[1]开始 层序排列 [k]的左儿子是2k 右是[2k+1]

操作

Delete Minimum

删除根最后一个元素代替根元素向下调整:选取当前节点和较小/大儿子(参考是小顶堆还是大)(通过下标定位),如果顺序不对则交换,直到顺序正确停止.

Insert

添加到末尾向上调整:比较当前节点和父节点,如果次序不对交换.

Create

空列表按顺序插入,向上调整.

应用

k路归并

将每个列表的第一个元素加入小根堆导出最小的一个进结果列表,调整从这个被导出的元素原所属序列中新增一个(如果有),调整Until…

时间复杂度为$nlogk$

序列和的前n小元素序列

给出两个长度为n的有序表A和B, 在A和B中 各任取一个, 可以得到n²个和. 求这些和最小的n个. 可以看作长为len(A)的有序表*len(B)

A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <=…A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <=……A[n]+B[1] <= A[n]+B[2] <= A[n]+B[3] <=…然后k路归并截取n项.

并查集

并查集维护一些不相交集合S={S1, S2, …, Sr}, 每个集合Sr都有一个特殊元素rep[Si], 称为集合代表. 用途:验证节点和修改后的节点的连通性

Exp.

每个元素参与且仅参与一个集合每个集合间保证联通.每个集合有一个代表元素,作为根节点参与联通.不关心每个集合的结构,所以放在一个数组里也没差.上下级关系通过一个列表pre[n]维护.查找代表

操作

Makeset

创造一个新的集合{x}

Union

合并两个集合.

Findset

返回元素在集合中的代表.

例子以后加.