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

“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）

“Swinson农夫的公鸡”（得分=5）

“Swinson农夫”（得分=7）

那么从优先队列中检索的顺序如下：

“Swinson农夫”（得分=7）

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

“Swinson农夫的公鸡”（得分=5）

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

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

注意，优先队列中的数据并不一定是被排好序的，只能保证按优先级高低顺序提取。在以后的讲义中你将看到，称为堆的数据结构是一种实现优先队列的有效方式，这种方式并不会完全按顺序保存数据。

首都的警察局采用很多种不同的优先级判定函数。如你所料，最有争议的优先队列正是度假优先队列。这个队列仅按照当前剩余假期的天数来排序。之前有人提议过加入其他优先级因素，都被拒绝了。无论你选择的度假地是冰川、海滩或沼泽，都将被平等对待——只看你剩余的假期天数。当然，这样的优先队列最重视公平。它将确保下一名休假的警官是本年度休假最少的警官。