昨天看到学校 MSC 群发布了微软招实习生的消息,于是尝试投了简历(临时用 Vue 写的),没想到对方看得起在下,同意了安排面试。面试要考察算法,我对算法的了解几乎仅限学校的数据结构课,但是不慌,机会总要争取一下,冲!目前学校课程不少,除了上课,好几个科目有期中考试,实验也有一堆,最累的还属手上的 App 项目。于是为了准备面试,所有休息时间(除了睡六七个小时),都得拿来刷题。

今日目标

  • 堆和堆排序
  • 优先队列
  • 拓扑排序和死锁检测
  • 并查集
  • Kruskal & Prim

若有树,任取其某一局部,都满足根节点大于等于子节点,则这个树是一个最大堆。同理有最小堆。

如何建堆

建立小根堆的例子:(下面用方括号指出调整的根)

建立堆的过程,颇有分形艺术的感觉。首先我们跳过最末元素 49, 27, 13, 76因为它们是叶子节点,对于每一个,自身已经是堆 —— 因为没有子节点。因此调整的起点是第 $\lfloor n / 2\rfloor$ 个元素,也即 0 起的 v [n/2 - 1]

let v = [49, 38, 65, 97, 76, 13, 27, 49]
/*
      49
     /   \
   38     65
  /\       / \
 [97] 76  13  27 // 调整的起点是 97
 /
49
*/

目标是将 97 的子树(

  97
  /
49

)变成堆:

/*
      49
     /  \
   38    [65] // 然后我们处理 97 的前一个元素 65
  /\     / \
 49 76  13  27
 /
97

      49
     /  \
   [38]    13 // 处理再往前一个元素
  /\     / \
 49 76  65  27
 /
97

      [49] // 处理再往前一个元素
     /  \
   38    13
  /\     / \
 49 76  65  27
 /
97

      13
     /  \
   38    [49] // 如果与子节点发生了交换,那么子节点所在树要重新调整
  /\     / \
 49 76  65  27
 /
97


      13
     /  \
   38    27
  /\     / \
 49 76  65  49
 /
97

完成,构成了小根堆,并找出了最小元素 13.

*/

参考此处

将无序序列顺存,当作完全二叉树。

所有叶子已经是堆(无子节点,相当于子节点是 0),从最后一个非叶子进行调整。

  • 如何找到最末非叶子?就是 N/2 向下取整。
  • 调整哪里?以最末非叶为根的子树调整。
  • 如何调整?挑选儿子其中更小的,与自己比较然后交换!(建立小根堆,则交换使得根更小)
    • 如果交换了,那么要检查交换后的子节点的树,可能需要重新调整。
  • 调整完呢?调整之后的最末非叶子!(N/2 - 1

如此处理直到根节点搞定。一轮之后,根将会变成最小元素。

如何调整堆

拿出 H 的根(输出),然后把 last (H) 作为新根。

比较新根的左右孩子,同其中更小的交换。交换之后它的孩子变了,如果还有孩子,就继续执行这一步。

堆排序

如何利用建堆实现堆排序?前面的例子看出,堆排序能够选择出最小的元素。那么对于剩余的元素,再次进行堆排序,可以选择出第二小的元素。

  • 初始堆化的时间:$O (n)$
  • 一次堆化的时间(插入性能):$O (\log n)$
  • n-1 次循环时间(排序性能):$O (n\log n)$

因此时间复杂度为 $O (n) + O (n \log n) = O (n \log n)$

练习

912. 排序数组 - 力扣(LeetCode) (leetcode-cn.com)

参考实现:

#include <debug.h>

void adjust(vector<int> &v, int bound, int i) {
  // 子节点索引
  int i_left = 2 * i + 1;
  int i_right = i_left + 1;
  // 选出比根大的子节点
  int i_max = i;
  i_max = i_left < bound && v[i_left] > v[i_max] ? i_left : i_max;
  i_max = i_right < bound && v[i_right] > v[i_max] ? i_right : i_max;
  if (i_max != i) {
    // 让小的靠根
    swap(v[i_max], v[i]);
    // 调整变化后的子树
    adjust(v, bound, i_max);
  }
}

void heap_sort(vector<int> &v) {
  // 构建大根堆
  int n = v.size();
  for (int i = n / 2 - 1; i >= 0; i--) {
    adjust(v, n, i);
  }
  // 选择排序
  for (int i = n - 1; i != 0; i--) {
    swap(v[0], v[i]);
    adjust(v, i, 0);
  }
}

class Solution {
public:
  vector<int> sortArray(vector<int> &nums) {
    vector<int> ret(nums);
    heap_sort(ret);
    return ret;
  }
};

int main(int argc, char const *argv[]) {
  Solution s;
  vector<int> arr = {8, 1, 14, 3, 21, 5, 7, 10};
  auto sorted = s.sortArray(arr);
  print_vec(sorted);
  return 0;
}

优先队列

优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用**[堆](https://zh.wikipedia.org/wiki/ 堆_(数据结构))**来实现。

优先队列至少需要支持下述操作:

  • 插入带优先级的元素(insert_with_priority)
  • 取出具有最高优先级的元素(pull_highest_priority_element)
  • 查看最高优先级的元素(peek):O (1) 时间复杂度

其它可选的操作:

  • 检查优先级高的一批元素
  • 清空优先队列
  • 批插入一批元素
  • 合并多个优先队列
  • 调整一个元素的优先级

——优先队列

我们先看看 C++ 自带的优先队列怎么用。

C++ 优先队列

头文件:#include<queue>

下面定义一个升序优先队列。队列顶部是最小的。

priority_queue <int,vector<int>,greater<int> > q_asc;
// 送入值,送的过程中自动排好序
q_asc.push(...);
// 取出队中最小值
auto min_of_q = q_asc.top();

样例(P215 解):

#include <debug.h>
#include <queue>
class Solution {
public:
  int findKthLargest(vector<int> &nums, int k) {
    priority_queue<int, vector<int>, greater<int>> q;
    for (auto num : nums) {
      // 随便送入 k 个数字到 q
      if (q.size() != k) {
        q.push(num);
      }
      // 然后把最小的换走,剩下 k 个最大的
      else {
        auto min_of_q = q.top();
        if (num > min_of_q) {
          // 置换
          q.pop();
          q.push(num);
        }
      }
    }
    return q.top();
  }
};

int main(int argc, char const *argv[]) {
  Solution s;
  vector<int> v = {3, 2, 3, 1, 2, 4, 5, 5, 6};
  cout << s.findKthLargest(v, 4) << endl;
  return 0;
}

练习

215. 数组中的第 K 个最大元素 - 力扣(LeetCode) (leetcode-cn.com)

拓扑排序和死锁(环路)检测

拓扑排序可以用于 Dependency Resolve,可以实现高级语言中的 Auto wire,以及资源管理中的调度。简而言之可以将依赖图(必须是有向无环图,Directed Acyclic Graph,DAG)处理为一个序列,从而保证序列中每个元素不会依赖它后方的依赖。另外拓扑排序还能检测出环路(循环依赖),所以理论上可以用进静态分析,作死锁预防。

我们先看看拓扑排序怎么做,然后再考虑代码实现。

【例子】对下面的图进行拓扑排序

automaton

首先找谁的依赖为 0. 显然是 E,F。因此第一序列 {E,F}。这样去除了对 E,F 的依赖:

automaton

注意到 B 的出度是 0,因此第二序列 {B}. 同理可得 {A},{C} ,{D}

因此拓扑排序的结果:

{E,F},{B},{A},{C},{D}

根据需要,可以输出线性序列,比如 E, F, B, A, C, D

思路:

输入有向边表

输入是有向边的列表。比如:

c -> a
c -> b
c -> f
d -> c
a -> b
b -> e
d -> e
d -> f

我们找到 a, b, c, d, e, f 中不依赖其它的:

e
f

然后删除对 ef 依赖的

c -> a
c -> b
d -> c
a -> b

找出 a, b, c, d 不依赖其它的:

b

删除对 b 依赖的:

d -> c
c -> a

如此,如果列表清空,则依赖可以解决。并且我们找 “不依赖其它的” 的出队序列就是拓扑排序。

考虑环路:

a->b
b->a

这种情况下,没有不依赖其它的,而列表非空,则说明存在环路。

参考代码:

注意一下删除 vector [i] 怎么写!

#include <cstring>
#include <debug.h>
#include <map>
#include <queue>
// 构造邻接表。也可以直接用数组下标做 map
// edge: a <- b
//       a <- c
// return list[a] = {b, c}
map<int, vector<int>> build_adjacency_list(int n_node,
                                           vector<vector<int>> edges) {
  map<int, vector<int>> adj_list;
  for (auto e : edges) {
    auto to_node = e[0];
    auto from_node = e[1];
    auto itr = adj_list.find(to_node);
    // create if not exists
    if (itr == adj_list.end()) {
      vector<int> adjs;
      adj_list[to_node] = adjs;
    }
    adj_list[to_node].push_back(from_node);
  }
  return adj_list;
}

void print_adjacency_list(map<int, vector<int>> adj_list) {
  for (auto it = adj_list.begin(); it != adj_list.end(); it++) {
    cout << it->first << " <- ";
    for (auto adj : it->second) {
      cout << adj << " ";
    }
    cout << endl;
  }
}

class Solution {

public:
  bool canFinish(int n_node, vector<vector<int>> &edges) {
    int outdeg[n_node];
    queue<int> topo_q; // 保存拓扑序列,提交 OJ 时可以去掉
    map<int, vector<int>> adj_list = build_adjacency_list(n_node, edges);
    print_adjacency_list(adj_list);
    memset (&outdeg, 0x0, n_node * sizeof (int)); // 注意细节
    // 规定 a <- b 表示 b 依赖 a,则 b 的出度表示 b 依赖多少个节点
    // 统计所有节点的出度,构建邻接矩阵
    for (auto e : edges) {
      // e[0] <- e[1]
      outdeg[e[1]]++;
    }
    // 将所有出度为 0 的节点入栈
    stack<int> s;
    for (int i = 0; i < n_node; i++) {
      if (outdeg[i] == 0)
        s.push(i);
    }
    int out_counter = 0;
    while (!s.empty()) {
      // 顶点输出
      int node = s.top();
      s.pop();
      out_counter++;
      topo_q.push(node);
      cout << node << endl;
      // 处理依赖
      auto adjs = adj_list[node];
      for (auto adj = adjs.begin(); adj != adjs.end();) {
        // 对每个依赖,减少出度
        outdeg[*adj]--;
        // 如果出读为 0,则压栈
        if (outdeg[*adj] == 0) {
          s.push(*adj);
        }
        // 删除弧
        adj = adjs.erase(adj);
      }
    }

    // 相等则无环
    return out_counter == n_node;
  }
};

int main(int argc, char const *argv[]) {
  Solution s;
  vector<vector<int>> dep1 = {{0, 10}, {3, 18}, {5, 5},  {6, 11},
                              {11, 1}, {13, 1}, {15, 1}, {17, 4}};
  cout << s.canFinish(20, dep1) << endl;
  return 0;
}

练习

检测环路:207. 课程表 - 力扣(LeetCode) (leetcode-cn.com)

并查集

好家伙,现在已经 0:19 了,说好的今天之内学完,看来有点困难。继续肝!

并查集 是一种多树结构,在数据库系统等地方使用广泛,支持两种操作:

  • 查找(Find):确定某个元素处于哪个子集;
  • 合并(Union):将两个子集合并成一个集合。

代表元:即集合的代表节点。用集合中的某个元素来代表这个集合,该元素称为集合的 代表元。(可以类比离散数学中的等价类 / 陪集)代表元是所代表集合的根节点。

我们可以把一个集合按照某种关系进行划分,成为集合的集合。每个子集合中的各个元素等价,任何一个可以选出来作为代表。

查找其实也是查找代表等价类,也就相当于查找代表元,也就相当于查找根节点!

合并其实就是合并到一个等价类。

同理,一个集合内的所有元素可以组织成以代表元为根的树形结构,这种结构称为集合树。如下图所示:

  1
 / \
2   3
    / \
   4   5
元素 代表元
1 1(并查集的根节点具有特点:自指
2 1
3 1
4 3
5 3

一个并查集可以由一个或多个集合树组成

代码实现并查集

我们的有两棵树:

    2           0
   / \           \    
  1   3           4
 /
5

现在要对它建模。

对于父子关系:定义表 parent [node] 表示 node 的直接代表是 parent [node]

则上面的树建模为:

node parent[node]
2 2
1 2
3 2
5 1
0 0
4 0

现在可以进行哪些操作?

Find “查”- 寻根

根就是两个代表集合的最上方的代表元,或者说集合树的根元素。利用根自指的特性判断是否是根

int find(int node){
    while(node != parent[node]){
        node = parent[node];
    }
    return node;
}

Union “并” - 合并集合树

就是把两个节点联系起来 —— 先找到各自的根节点,再把其中一个元素的根节点连接到另一个元素的根节点上:

void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) {
          return;
    }
    parent[rootX] = rootY;
}

路径压缩

路径压缩:将对某个祖节点的间接依赖转换为直接依赖。可以有效降低树的高度。

如下图,如果我们只关心各个节点和 1 的关系,那么就可以压缩 {4,3}, {5,3} 这两对的关系。

image-20211110002423352

隔代压缩:

int find(int node){
    while(node != parent[node]){
-       node = parent[node];
+       node = parent[parent[node]];
    }
    return node;
}

彻底压缩:

int find(int node){
    if (parent[node] != node) {
        parent[node] = find(parent[node]);
    }
    return parent[node];
}

按秩合并

:从为从根节点开始其叶节点最长的一条树链上结点的个数。

启发式按秩合并:进行 Union 操作时,不盲目合并,而是先计算树高,将秩小的树接在秩大的树下面,这样就可以尽可能避免树的高度的暴涨。

练习

并查集知识点题库 - 力扣(LeetCode) (leetcode-cn.com)

Kruskal & Prim

昂,现在已经一点了。冲刺冲刺!

这俩算法用于求解最小生成树。

最小生成树

最小生成树(Minimum spanning tree,MST)是一副连通加权无向图中一棵权值最小的生成树。

Kruskal

将原图中所有的边从小到大排序。从最小边开始,如果这条边两边的节点不连通,则添加这条边。(换言之,添加后不成环)重复直到再添加就要成环,停止。

为什么 Kruskal 算法能求出 MST?

【例子】对于下图,假设其边无向,求其 MST

image-20211110011000591

解:

将边排序:

边权
BC 1
CD 2
AE 3
EF 4
DF 6
BF 7
FC 8
AF 9

然后加边:

边权 能不能加?
BC 1 1
CD 2 1
AE 3 1
EF 4 1
DF 6 1
BF 7 0
FC 8 0
AF 9 0

得到如下图:

image-20211110011717515

这就是最小生成树。

Prim

这个算法思想很类似 Dijkstra。

先随便选择一个顶点作为初始顶点,再选择与之连接的顶点中,边的权重最小的顶点作为下一个顶点(并且不能成环),依次按照这个规则选择顶点,一直到所有顶点都遍历完为止。

参考

秩平衡树 (Rank Balanced Tree) - riteme.site

图解并查集,附赠几道 Leetcode 练手题 - SegmentFault 思否