算法 – 第 2 页

简易优先队列 js 版

这个优先队列使用数组存储。下面的代码是一个最大堆的实现。

计划把学习的系列排序算法做个简单的动画，坚持做到 timsort 为止。

就这么一简单玩意儿，花了我一晚上时间，我怎么变得聪明起来呢。

近期一直在玩的游戏是汉诺塔，我倒是觉得这个游戏挺解乏的，但是我女票子却不喜欢，我让她玩 5 层，她讨价还价成 4 层，我再坚持一次，她就说不玩了不玩了，那就陪她玩 4 层咯。下面，我们来看看 js 制作的简单动画展示，这个游戏应该怎么玩。

有一个二维数组如下：

let arr = [["a0", "a1"], ["a1", "a2"], ["a3"]];

我们看到 a1 这个元素在数组的第 0 项和第 1 项都存在了，我们需要将其合并成一项：

// 需要转化成 [["a0", "a1", "a2"], ["a3"]]

同理，针对一个任意项的二维数组，只要其中某单个元素重复了，就应该合并进同一个数组里，减少这个二维数组的个数。那么怎么实现这个呢？

因为工作的关系，不得不学习了几种算法，好久不用又忘记了，这是一篇复习文章。

并查集回答的是连接问题，比如说从 a 城到 b 城有没有路，能回答有或者没有，但是不能回答具体的路是那几条，该怎么走；再比如说 a、z 这 2 个人能否通过共同好友的名片分享来加上微信。

并查集是解决点与点之间的关系，遇到实际问题的时候，需要我们进行转换成点与点，也就是建模。在数据结构上一般用数组来存储这些点。

这篇文章来自工作中的一个实际问题：电子工程师在进行电路设计时，一般不用画出有闭环的导线，否则就短路了，这个是没有意义的。为了避免电子工程师的误操作，需要做这么一个防呆的工作。这是一个实际的场景，为了解决这个问题，可以转换成一个图的问题。

先来解释几个概念。

本站以前有一篇文章提到了 prim 算法的实现，具体点这里，我写了完整的示例，和优化版的 prim 在时间上的对比。现在我们来看另一种思路：Kruskal。

话不多说，先看实际效果和结论。在 1k 个节点里，lazy prim 耗时在 4s 左右，优化后的 prim 在 900ms 左右，而更高效的 Kruskal 在 600ms 左右。测试的前提条件是基于我的电脑硬件配置和 1k 个节点的完全稠密图。

要实现高效的 Kruskal 算法，需要基于高效的并查集数据结构，但是并查集我们不在这篇文章里谈及，我们主要谈谈 Kruskal 的思路。