数据结构

并查集

  并查集重点在于通过集合维护什么额外信息来解决问题。额外信息可以是集合内元素数量、当前元素和根节点的距离。当前元素和根节点的距离可以用来维护多个相互关系。

堆

  在动态的求中位数时，可以用对顶堆，上边是一个小根堆，下边是一个大根堆，用来维护中位数在中间。