本文针对堆的应用场景总结一些例题和思路，并对并查集的整个思路进行梳理，以及代码规范化。

堆

题1：Top K Frequent Elements

思路：较为模板，求前 k 大，用小根堆，求前 k 小，用大根堆，大小特性是特定的。

关于不同语言的使用：

  • 在python中，默认是小根堆，即根节点对应的值是最小值
  • 在java中，默认是小根堆
  • 在c++中，默认是大根堆，如果需要，需要使用greater()转换成小根堆

一般逻辑为下：

from heapq import heappush, heappop, heapreplace
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        d = collections.Counter(nums)
        res = []
        num = []
        for key,value in d.items():
            if len(res) < k:
                heappush(res,(value,key))
            elif value > res[0][0]:
                heapreplace(res,(value,key))
        for val,key in res:
            num.append(key)
        return num

题2：Ugly Number II,Super Ugly Number

思路1：多指针+动态规划。指针指向的是乘以当前质因数能维持最小值的ugly number，根据指针对比进行状态更新。

思路2：堆，但是堆的空间是$O(n*k)$，相对来说比动态规划的空间要大一些。

并查集

题1：Most Stones Removed with Same Row or Column

思路1：连通分量的概念，每次移出连通分量中石子数目-1的点。连通分量的话，使用DFS和Union-Find都是可以的。

class Solution {
    public int removeStones(int[][] stones) {
        int N = stones.length;
        int[][] graph = new int[N][N];
        // 也可以建立邻接表，其实都是一样的，遍历的方式不同而已。

        for(int i=0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(stones[i][0]==stones[j][0] || stones[i][1] == stones[j][1]){
                    graph[i][j] = 1;
                }else{
                    graph[i][j] = 0;
                }
            }
        } 
        int res = 0;
        boolean[] visited = new boolean[N]; //default: false
        for(int i = 0; i < N; i++){
            if(visited[i] != true){
                // 重新建连通分支，且要减个一
                Stack<Integer> stack = new Stack();
                stack.push(i);
                res--;
                visited[i] = true;
                while(!stack.isEmpty()){
                    int node = stack.pop();
                    res++;
                    for(int j=0; j < N; j++){
                        if(graph[node][j]==1){
                            if(visited[j] != true){
                                visited[j] = true;
                                stack.push(j);
                            } 
                            }
                        }
                    }
                }
            }
        return res;
        }
   }

思路2：并查集

这里对并查集的概念梳理一下，做个总结。

步骤：初始化，将所有节点看作一个只包含自身的集合树，如果只包含自身，则元素已经是根节点（代表节点），那么pre[i]==i，之后通过Union-Find-Union…来形成一定数量的连通分支。

class DSU:
    # 将p作为指针数组，指向代表节点。
    def __init__(self,N):
        self.p = list(range(N))
    
	# find-寻父函数
    # 若x!=p[x]，则p[x] = find(p[x])
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]

	# 印贼做父
    def union(self, x, y):
        xr = self.find(x)
        yr = self.find(y)
        self.p[xr] = yr

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        N = len(stones)
        dsu = DSU(20000)
        for x,y in stones:
            dsu.union(x,y+10000)
        return N-len(set(dsu.find(x) for x,y in stones))

路径压缩：

路径压缩是将整个并查集形成的树扁平化，上述代码也是一种实现方式，就是采用DFS将所有的父结点都用父节点所属的root node代替：

def find(x):
    if p[x] != x:
        p[x] = find(p[x])
    return p[x]

在实现过程中，在find函数里加上parent[element] = parent[parent[element]]，将当前节点直接指向自己父亲的父亲节点，减少深度。

def find(x)
	while x != p[x]:
        p[x] = p[p[x]]
        x = p[x]
    return x

根据Algorithm书，最优化的解法是路径压缩+平衡，这里用python代码写一个Union-Find高效的写法：

class UF:
    def __init__(self, n):
        # 初始化每个节点都为单独的连通分支,且树的深度初始化为1
        self.count = n
        self.parent = [i+1 for i in range(n)]
        self.rank = [1 for i in range(n)]
        
   	def get_count(self):
        return self.count
    
   	def find(self,x):
        while x != self.parent[x]:
            self.parent[x] = self.parent[self.parent[x]] 
            x = self.parent[x]
		return self.parent[x]
    
    def is_connected(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x1 = find(x)
        y1 = find(y)
        if (x1==y1):
            return
        if self.rank[x1] > self.rank[y1]:
            self.parent[x1] = y1
     	elif self.rank[x1] < self.rank[y1]:
            self.parent[x1] = y1
        else:
            self.parent[x1] = y1
         	self.rank[y1] += 1
       	self.count -= 1

题2：Longest Consecutive Sequence

class Solution {
public:
    unordered_map<int,int> uf, cnt;

    int find(int i){
        return i == uf[i] ? i: uf[i] = find(uf[i]);
    }

    int merge(int x, int y){
        x = find(x); y = find(y);
        if(x == y) return cnt[x];
        uf[y] = x;
        cnt[x] += cnt[y];
        return cnt[x];
    }

    int longestConsecutive(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        for(int i: nums) uf[i] = i, cnt[i] = 1;
        int ans = 1;
        for(int i: nums){
            if(i != INT_MAX && uf.count(i+1)) ans = max(ans, merge(i, i+1));
        }
        return ans;
    }
};

题3：Accounts Merge

思路：并查集的作用就是建立不同元素之间的联系，即建立同属一个root node的连通分支，这里是建立不同邮箱账号之间的联系。

题4：Smallest String With Swaps

思路：因为交换可以任意次，即可利用所有能够交换的index做连通分支，连通分支内部再做一个排序。

class DisjointSetUnion {
private:
    vector<int> f, rank;
    int n;

public:
    DisjointSetUnion(int _n) {
        n = _n;
        rank.resize(n, 1);
        f.resize(n);
        for (int i = 0; i < n; i++) {
            f[i] = i;
        }
    }
    int find(int x) {
        return f[x] == x ? x : f[x] = find(f[x]);
    }

    void unionSet(int x, int y) {
        int fx = find(x), fy = find(y);
        if (fx == fy) {
            return;
        }
        if (rank[fx] < rank[fy]) {
            swap(fx, fy);
        }
        rank[fx] += rank[fy];
        f[fy] = fx;
    }
};

class Solution {
public:
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        DisjointSetUnion dsu(s.length());
        for (auto& it : pairs) {
            dsu.unionSet(it[0], it[1]);
        }
        unordered_map<int, vector<int>> mp;
        for (int i = 0; i < s.length(); i++) {
            mp[dsu.find(i)].emplace_back(s[i]);
        }
        for (auto& [x, vec] : mp) {
            sort(vec.begin(), vec.end(), greater<int>());
        }
        for (int i = 0; i < s.length(); i++) {
            int x = dsu.find(i);
            s[i] = mp[x].back();
            mp[x].pop_back();
        }
        return s;
    }
};