几个星期以前，我用 Clojure 实现了 Dijkstra 算法。这个核心算法只有 25 行。这些代码是我匆匆做出来的，当时我正在和黑客学校的一些人混在咖啡店里。我在一个数据集上运行了我的程序，这个数据集是一张密集交织的图，里面有 200 个节点。在 200 毫秒内，这个程序产生了一个起始节点到图中其它所有节点的最佳路径。

我关掉笔记本，吃完花生酱、香蕉和蜂蜜三明治，和朋友告别，然后在这个下午剩下的时光里，我徘徊在下东城尘土飞扬的阳光下。

到周一晚上，我的生活开始崩溃了。

Dijkstra 算法用来计算图中的一个节点到另一个节点的最短路径。如果把节点比作英国的城市，那公路就是各个节点间的连接，Dijkstra 可以用来规划伦敦到爱丁堡的最短路径。这里的关键是“规划”。这个算法是先勘查，再上路。

想象你就是这个算法。你首先检查所有和伦敦直接相连的城市，也就是那些只通过一段路就能到达伦敦的城市。记录下伦敦和每个直连城市之间的距离。并记住你已经考察过伦敦了。然后你关注公路上距离伦敦最近的城市，比如说布莱顿。再检查每个直接连到布莱顿的城市。记住要跳过伦敦，因为你已经考察过它了。紧接着，针对每个城市，你记录（更新）伦敦到布莱顿再到这个城市的距离。然后记住你已经考察过布莱顿了。你现在关注下一个未被考察且距离伦敦最近的城市。像这样继续，直到你的目的地（爱丁堡）作为下一个关注的城市出现为止 。此时，你就找到一条通往爱丁堡的最短路径。

周一早上，在黑客学校的签到会上，我高兴地报告了我将利用后面几天用 Clojure 去实现一个 Fibonacci 堆。

我读过 Dijkstra 维基上的一篇文章，说有两个人发明了 Fibonacci 堆，并用它做节点选择，从而减少 Dijkstra 算法的运行时间。Dijkstra 算法还是做路径规划。Fibonacci 堆只是帮着快速找到下一个被考察的城市。

查找是一个费时的过程。你必须仔细查找列表中所有未被考察的英国城市，找到一个距离伦敦最近的城市。我在咖啡店里所实现的 Dijkstra算法，代码遍历了整个列表才返回一个距离最短的。这是很慢的。

Fibonacci 堆利用另外一种方法解决了这个问题。它按照距离伦敦的远近对这些城市进行排序。因此当你想要找到下一个考察的城市，你只要选头一个就好了。

为了解释，我必须把城市和公路的比喻抛到脑后。非常遗憾，我找不出一个新的比喻来代替。堆不是很像家谱图，也不是很像生长的绿色树木。而是这样一幅图：

这是一个普通的堆。Fibonacci 堆只是更复杂一点，但思想是一样的。每个圆圈 —— 每个节点 —— 拥有零个或者更多的子节点。而且，每个节点包含一个数字标记。这是它的排序数值，或称为键。这些节点都连接到一个树上，最低键值的节点作为根节点。

我开始通过画图来演示 Fibonacci 堆的关键操作是如何被应用在虚构的 Fibonacci 堆上。在反复阅读了这篇 Wikipedia 文章后，我画出了每一个操作。

到周一结束时，我画出了一片森林。我已经掌握了这个算法，我有信心把它解释给 Vera 和 Pepijn。（译者注：Vera 和 Pepijn 是作者的两个合作者，后面会提到）

那天晚上我躺在床上，等着入睡，我意识到我正在思考 Fibonacci 堆。我的噩梦开始了。

周二我去黑客学校，又花费了一天时间在笔记本上写写画画。这时我已经得出了这个核心算法的伪代码框图。

早上我搭乘 G 线火车，换乘 C 线火车后到达学校。我已经阅读过《如何解决它》，这是一本经典的数学读物，介绍了一种非正式的解决问题的通用方法。对于《算法导论》，我也曾半生不熟地思考过，这本书里面研究了操作列表、树、堆和图表的算法。
 

回首那段日子，并意识到你当时沉浸在你所做的事情里，是一种很棒的感觉。你的工作浸入到你的旅行，你的谈话和你的人际关系当中。我并不是说你抬头看到树木在风中嘎嘎作响，就一定要仿佛像看到倒挂的 Fibonaccci 堆一样。比那样简单得多。你一直在思考你的工作，无论当你站在 Sunburnt Cow 外拥挤的人行道上，抑或是当你和你爸爸讨论《高架桥下的车行道》中砂岩的笔触如何展示出太阳光的耀眼的时候。你的工作只是轻轻地与你同在，就像一个背景故事或是一个看不见的朋友。（译者注：《高架桥下的车行道》是梵高所做，布面油画 32.7 x 41.0 cm　巴黎1887年春）

因此我在接下来的两周里都沉浸在数学和堆里。我在淋浴时思考它们。我在 G 线火车上思考它们。我在这个酒吧思考它们。（关于这个酒吧，）我和其他一些黑客学校的人一起来来这里参加一个巴萨诺瓦晚会，起因是之前在等火车的时候，我听了几分钟 James 的 iPod，以为巴萨诺瓦是一种鼓声沉重的，类似萨尔萨舞曲的音乐，结果发现它实际上比较轻、更加灵巧、听上去像一个蹦蹦跳跳的理发店四重奏。（译者注：断句，断句，断句，重要的事情说三遍！）

在2011 年 JSConf US 会议上，我在讲演中谈到了代码和生活在 Pistol Slut 上是如何相映成趣的。但这次，代码带给我忧心超过了怡趣。我开始睡不好，不知道要花多长时间来完成这件事让我百爪挠心。这些讨厌的问题不是间隔几个月，而是被压缩到几周内。这些代码已经不是一个编外项目，而成了我的全职工作了。我用 Clojure 编写，而不是用相对简单的 JavaScript 编写，这真的让我脑洞打开，说多了都是泪啊。

我开始编写代码。我很快发现树的数据结构对于 Clojure 这种不可变状态的语言来说显得太复杂了。因为改变一个节点需要重新构建这个树中的大部分。想象你给树远端的一个节点增加一个子节点。你必须复制包含这个父节点祖先在内的所有节点和分支。这是很花时间的，而且占用了大量的内存。

Pepijn 建议我尝试一个解决方案：一种叫做 zipper 的概念。这种结构把你当前关注的节点作为一个树，树中的剩余部分都是透过当前节点观察的。以这个树为例：

一个聚焦在 J 节点的zipper看上去像这样：

回想这个假想的母节点。由于这个树是模拟一个zipper，所以很容易生成。我准备建立一个新的zipper，它融合了前一个子zipper的可重用部分和代表这次改动的新部分。所需的时间和内存取决于原始状态有多少可以使用。这个例子里，我可以重用路径和左右的上下文。所以我必须创造的新东西只是一个由新节点 L 组成的新焦点，由节点 L 和它的父节点 J 组成：

如果你想要更加了解zipper的概念，我推荐你阅读这篇很棒的文章，前面的例子就选自这里。

继续这个故事。

在接下来的两天，Vera和我埋在代码里。当黑客学校展示日到来时，我们没有什么东西可以演示。我们只有谈论 Fibonacci 堆算法的工作方式。

Vera 解释说 Fibonacci 堆不是一个堆（树），而是一个自我包含的子堆（树）列表。她说有一个最小指针指向排序值最小的子堆根节点。我不记得她是否用了地图里城市的比喻，如果用了的话，那么在这个比喻中，节点上的键就是起点城市到节点的距离。 

她解释了 Fibonacci 堆的核心操作。

她说合并是一个新节点加入 Fibonacci 堆的方式。这个节点作为一个新子堆的根节点被插入。如果这个新节点的排序值比当前最小指针指向的节点要小，就需要更新指针。

她说查找最小是让指针指向最小的根节点，跟随它并返回这个节点本身。

她说提取最小是让指针指向最小的根节点，跟随它并在它所属的子堆中去除这个节点。 

她演示了提取最小如何整理这些子堆，即遍历这个节点的所有子节点并确保每一个进入一个新的独立堆。 

她展示了提取最小如何通过合并进一步整理这些子堆，即将有相同数量直系后代的子堆配对组合在一起。  

她解释了减键操作是如何工作的。第一步是简单地减少一个节点的排序值。如果这个减法让这个键比父节点的还要小，那必须从这个子堆去除这个节点，让它作为新子堆的根节点。还要更新这个最小指针让它指向新的最小根节点。  

她解释说，如果任何节点在一次减键操作中失去不止一个孩子，那这个节点自己也要成为一个新的子堆。  

第二天是星期天，我整个下午都坐在一间阳光下的咖啡店里，稍稍从混乱中得到一些喘息。我编写的代码脱离了主要的问题。它根据一个简明的树结构生成 Fibonacci 堆。这样更容易编写测试，因为它容易产生在某种测试场景下所需要的Fibonacci 堆。

第二周的周一和周二 ，Vera和我重新回到混乱中，我们开始实现减键以完成 Fibonacci 堆。我们在周六（演示日）把它放到我实现的 Dijkstra 算法中。我们慢慢发现一个可怕的现实 。无论是过去还是现在我可以说 ，不变状态语言编写的 Fibonacci 堆 不适用于 Dijkstra 算法。事实上，它不适用于任何一个算法，只要这个算法依赖与 Fibonacci 堆不同却共享相同信息的数据结构。Pepijn在他的博客中谈到了这个普遍的难题，命名为双索引问题。

Fibonacci 堆实现的 Dijkstra中，有两个数据结构。第一个是Fibonacci 堆。另一个是节点的图表，它告诉你哪个节点连到哪个城市（靠，我们又回到地图的比喻）。检查你当前关心城市的邻居可能会迫使你减小为邻居所存储的最佳路径距离。但这并不简单。当你得到附近城市的列表时，你正在查看这个图表的数据结构，它代表你手上有的图表节点。尽管这些图表的节点像 Fibonacci 堆中的节点一样代表相同的城市，它们在计算机里是完全不同的实体。因此去减少一个城市（堆节点）的键（距离），你必须从堆中得到代表这个城市的节点。这是很花时间的操作，因为要搜索整个堆 。

我将导演一场虚拟的问答，一个是假象的你，另一个是真正的我。

你：为什么对于可变值的语言来说，这不是一个问题呢？

我：因为图中的节点可以只包含一个指向 Fibonacci 堆中对应部分的指针。

你：什么是指针？

我：它就像一个箭头标记，给你一条通向计算机所代表东西的直接快速路线。

你：为什么你不能使用这种指针？

我：我们可以，但是它们没有想要的效果。

你：为什么？

我：因为在不可变语言里，当你改变了数据中的一部分，你就需要一个完整的新副本。

你：天啊！这很烦人啊，为什么我不问你都不说细节呢。为什么完整的新副本会是一个问题？

我：抱歉。这的确是一个问题，因为当你更新一个节点的新距离时，作为改动的一部分你复制了这个节点。这个数据的其他部分可能还有指向这个节点的指针，但是它们现在指向的是旧版本 。在可变语言中 ，你可以只更新数据共享的一部分，而不用复制其他的。这样所有指向数据的指针都还是合法的。

你：明白了。

我们实现了 Fibonacci 堆的 查找操作。这个操作是给定一个节点，然后在 Fibonacci 堆中找到它。这个操作和 Fibonacci 堆的出发点正好相反。当我们使用这个操作是，原始版本的 Dijkstra 算法要比这个 Fibonacci 堆版本快两倍。

在黑客学校演示日上展示这些结果，是有点沮丧和滑稽的。但在对完成 Fibonacci 堆后的温暖和舒缓回味中，这些感觉都缓和下来的，不，都消失了。