启发式合并学习笔记

启发式合并是一种神奇的暴力,它经常用于合并两个只能一个个元素插入的集合

假设我们要合并两个集合 SSTT,那么显然小的集合里元素一个个插入大的集合是更优的。所以启发式合并就是将小集合中元素插入大集合来合并

这样做看起来很暴力,但因为一个元素 uu 所属的集合比另一个集合小的话 uu 才会被枚举插入,所以 uu 被枚举插入集合一次以后,它所在的集合大小至少翻倍

所以启发式合并的时间复杂度是 O(tnlogn)O(tn\log n) 的,其中 tt 是插入集合的时间复杂度

练习题目