24 用优先队列进行调查

“Donavan警长！”Notation走进办公室时，脱口而出。

“我想当面向您道歉，我在工作时间之外，未经授权就去调查案子。但这既是Frank调查的案子，也是我的，如果他报告……”

“这案子怎么变成你的了，Notation警官？”警长打断她，“我记得我派你去查假冒溜溜球的案子。可你为什么在Crannock的农场调查被盗的文件？”

“我在跟踪一条线索……”Notation说。

“你在跟踪一条线索？”警长打断道，“你的所有报告里，我没看到任何关于Array Cart的报告。”

“我是那天早上才想到的。”Notation解释道。

“所以，你决定自己跟踪这条线索，而不向负责这个案子的侦探报告？”

Frank皱起了眉头。警长特别执着于照章办事，在警长看来，得到线索不及时报告是非常严重的事情。从Notation慌张的言辞中，Frank看出她也是这么想的。

“我当时已经在农场的附近，”她说，“发现……”

“有线索？”Frank问。

“我记得失窃当晚，”她说，“我刚做完我的晚间值班报告，就看到窗外一辆奇怪的推车。当时我也没多想，因为鱼贩们总是喜欢用各种奇怪的推车。我以为是早晨鱼贩们交货用的。”

她转向警长，目光中流露出恳求之情。“这条线索看起来不大靠谱，”她解释道，“我觉得这条线索或许是条死胡同，那车可能只是交货用的。所以在查出更多情况前，我并不想报告。”

“然后你就和Frank一起查了几乎两整天？”警长说。

“我们发现了一些更有用的线索。”Notation道。

“Notation警官，”警长厉声道，“不知道是哪位前警长的鬼魂在引导你这样做。现在每个人都要遵守规章制度，而你没有。”

Notation死死地盯着地面：“我明白了，长官。”

“不，”警长说，“我不确定你是不是真的明白。但你会有足够的时间去反省。你被停职了，等候通知。”

Notation哆嗦了一下，但没有抗议。

警长转向Frank说：“Frank，你有工作要做了。”

当Notation转身离开时，她的视线凝固在了挂在墙上的Fredrick国王的肖像上。她似乎陷入了沉思。

“警长，”她突然停住说，“你有优先队列吗？”

Frank努力地回忆了一下，最后想起来他的一位教授曾在课堂上讲过Fredrick国王是如何推广优先队列方案的。

在Fredrick成为国王之前，他会倾听王国公民的投诉。由于时间紧迫，市民投诉繁多，他被迫需要制定一个优先队列方案。毕竟Fredrick王子一次能忍受的抱怨是有限的。

开始时，Fredrick王子试过使用投诉栈，优先选择处理最新的投诉，但后来他发现这样会错过那些重要的但很久以前的投诉。然后他尝试使用投诉队列，优先选择处理时间最早的投诉，然后他发现这样又会错过重要的近期投诉。最后，他采用了一种新的数据结构——优先队列——使得他每次都可以先处理最重要的投诉。

“优先队列？”警长问，显然被这个突如其来的问题问蒙了。警长训完话后几乎没有人敢接话。他们只是慢吞吞地小心翼翼地走出办公室，或者在某些情况下，还会被关在一间黑暗的杂物室里待上几小时。

“一种数据结构”，Notation胸有成竹地解释道，“就像普通的队列，你可以对元素进行入队和出队操作。区别是为每个元素增加了一个重要性的优先级分数。当一个元素出队时，优先队列就会为你提供下一个最重要的元素。”

看到警长和Frank貌似有些不理解，Notation举了一个例子：“如果我插入四个元素，优先级分别为1、2、4和3，那么我会按4、3、2、1的顺序提取它们。”

“我知道什么是优先队列，”警长说，“我们用它来存储噪声投诉清单。叫得越响，优先级越高，所以我们总是先解决最糟糕的情况。我听说他们也采用这种方法来处理附近污水臭味的投诉，虽然看起来那里的所有事项的优先级都一样——都令人非常难以忍受。不过，你想说什么？”

“您这里有优先队列吗？”Notation问道。

警长摇摇头，感到迷惑不解，并压制着自己的愤怒：“没有多余的了”，他说，“所有的优先队列都已经投入了使用，有一个用于噪声投诉，有三个用于不同类型的犯罪，还有一个用于最高通缉犯，最后一个用于度假申请的安排。你想说什么？”

“最佳优先搜索。”Notation说。

“最佳优先搜索？”警长问道，“Frank告诉我，他使用的就是最佳优先搜索。”

“没错。”Frank点头道。

“优先队列会更有效率，”Notation解释道，“每次我们找到一条新线索，就可以把它放到优先队列中，通过其得分来显示该线索的质量。接下来，当我们准备调查下一条线索时，就可以从优先队列中提取最有用的线索。这样，我们总会按照下一条最有用的线索进行调查。”

Frank叹了口气，摇了摇头。他知道警长完全能猜出这番谈话的目的。警长擅长给大家上课，他不会凶巴巴地骂人或说脏话，但会以平静的方式让一名新警官意识到自己的愚蠢。“你之前是怎么做的？”警长耐心地问。

“我把线索都记在一个笔记本里，”Notation答道，“每次我们准备调查一条新的线索时，我就会看一遍整个清单，找到最好的那个。”

“那你有多少条线索呢？”警长问道，“平均而言。”

“平均而言？”Notation想了一会说道，“我猜有二到五条吧。”

“你想让我使用优先队列来处理只有二到五条记录的列表吗？”如果警长采用他一贯吼叫的方式来问，那这个问题听起来可能不太严重。相反，他的冷静和耐心的口气让整个讨论的不必要性更突显了。

Notation脸红了。“嗯，优先队列并不是很昂贵……”她开口道，话没说完又咽回去。

“Notation警官，”警长说，“我同意优先队列对于最佳优先搜索很有用。待会我就可以订购一套全新的系统，每个侦探配一套。但现在你还用不到，因为你还没有足够多的线索，而且更重要的是，这案子不归你管。”

警长越说，Notation的脸越红，现在已红得像甜菜汤了。她深吸一口气，直视警长的眼睛，咕哝道：“我明白了，长官。”

Frank感到非常遗憾。Notation犯了典型的菜鸟错误，过度优化解决方案。他得告诉她使用优先队列来追踪线索的想法是完全合理的，事实上，他一直在使用优先队列。然而，她问问题的时机却糟到不能更糟了。