24 用优先队列进行调查（第2/3页）

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

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

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

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

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

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

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

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

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

“Notation，”警长继续说，“你在这里很有前途。你聪明、上进、有良好的直觉。但是你必须学会服从命令。别最后像Frank那样。”

Notation想开口抗议，但她看了一眼Frank，扮了个鬼脸，然后紧闭着嘴，一声不吭。她微微点点头，敬了个礼，大步走出办公室。

“Frank，你现在有得忙活了。去吧。”

Frank转身跟着Notation出去，连头都懒得点一下。

直到来到楼梯前，Frank才开口说话。

“你应该知道Orb区有一个行家，能帮你做便宜的优先队列，他叫Heaperous。他只在上午工作，所以你得等到明天才能找他。”

Notation停了下来，非常疑虑地看了他一眼，问道：“你为什么要告诉我这个，Frank？”

Frank努力做出同情的表情：“我听了警长的许多长篇大论。更重要的是，我知道好的数据结构对于调查的价值。”

“如果好的数据结构更有价值，那你为什么不使用优先队列？”她反问。

Frank恼怒地看着她说：“我当然在用优先队列。一开始我就一直在用。你以为我一直在用脑袋瓜子记所有的线索吗？”

“什么？”Notation道，“搞了半天，你一直在用优先队列啊？你为什么不跟警长说？”

Frank笑道：“菜鸟，你还要多了解一下警长。首先，警长在对任何东西夸夸其谈时，你不要去打断他。我曾经看到一名侦探被调职去做一个月的笔录，就是因为警长在大声评论豆腐的时候被他打断了。”

Notation盯着Frank，不知说什么好。

“关键是，”Frank继续道，“有时候你需要自己动手。如果优先队列可以帮到你，不要等着批准。出去买一个用就行。”

Notation考虑了一下这个建议。最后她点了点头：“从技术上而言，购买自己的装备不违反任何政策。谢谢你，Frank。”

Notation脸上的兴奋几乎让Frank感到内疚。任何镇上行家商店里都可以做优先队列，大多数都与Heaperous的价格相当。但Heaperous所在的Orb区是市区范围内最远的一个，之所以告诉Notation这家店，是因为Frank需要确保Notation能在尽量长的一段时间里不妨碍自己做事。

警用算法导论：优先队列

节选自Drecker教授讲义

在警察的职业里会碰到的所有数据结构中，我保证最有价值的是优先队列。就像数据栈和队列，优先队列数据结构让你能插入数据，然后按特定的顺序删除数据。栈和队列的执行顺序由插入的元素决定，而优先队列通过优先级递减来给数据排序。下一个删除的元素是当前队列中优先级最高的元素，而无论该元素是何时插入的。

每个插入优先队列的元素也必须有优先级，或者叫分数。这可以是元素本身的价值，也可以根据不同的函数计算得来。

接下来我们来看看这个有关噪声投诉的案例，它是根据噪声的严重性进行优先排序的。如果按照以下顺序插入这些投诉：

“Exponentiated Expresso的伙计们”（得分=3）

“Crab’s Pinch船夫号子大赛”（得分=6）

“Swinson农夫的兔子”（得分=1）