leetcode 1202 交换字符串中元素 并查集+小顶堆

（1）使用并查集以字符串中的位置下标，连通字符串中的元素

class UnionSet:

    def __init__(self, n):
        self.father = list(range(n))
    def find(self, ind):#递归查找父节点的同时，将叶子挂在根节点下面
        if self.father[ind] == ind: return ind
        self.father[ind] = self.find(self.father[ind])
        return self.father[ind]
    
    def merge(self, x, y): #将y归入x所在集合中
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.father[root_y] = root_x

（2）每个元素的根节点创建一个小顶堆，存放同集合的元素

（3）每次弹出相应位置根节点的值，利用小顶堆的性质自动弹出从小到大的序列

class Solution:
    def smallestStringWithSwaps(self, s: str, pairs: List[List[int]]) -> str:
        n = len(s)
        us = UnionSet(n)
        for i in pairs:
            us.merge(i[0], i[1])
        my_dict = collections.defaultdict(list)
        for i in range(n):
            heapq.heappush(my_dict[us.find(i)], s[i])

        result = ""
        for i in range(n):
            result += heapq.heappop(my_dict[us.find(i)])

        return result