第二天一大早,Frank就从安全屋里溜出来,穿过市中心到警察学院去。只要到了学校,看到身边有很多警察、学员和退休警官,他就会觉得很轻松。他甚至笑着大摇大摆地走过了通往学院办公大楼的院子。
Frank很多年没有来这里了。学校有一条规定,需要教授们一直保持办公室的门是打开的,以方便学生随时来问问题。然而实际情况是只有很少的学生会主动利用这个学习机会,大多数学生则是到考试前一天晚上才意识到自己有多少不会的知识,Frank则要更晚,他一直要等到考完试看到卷子后才能发现自己有多么无知。
扫一眼大门口的教职工目录就可以发现,Loop教授占用了整个顶楼的私人办公室。Frank并没有感到惊讶。教职工大楼特殊的设计令办公室的分配备受争议。每层楼的办公室数量都是下面一层楼的二分之一。这意味着你在更高层享受更广阔美景的同时,办公室的面积也变成了下一层办公室的两倍。在几年的争抢后,院长颁布了一个基于教龄的严格规定——每个人的教龄必须比其楼下办公室的人的教龄要长。结果,他把教职工大楼变成了一个“堆”。
Olivia Loop博士是巫师犯罪学的教授,她的教龄有70年之久。只有研究浮点运算的Babbleton教授可以与她比肩,他有61年的教龄。
Frank走到最顶层时,他大口喘着气,在想95岁的老教授是如何爬上来的。不过她每天爬上爬下,也确实得到了锻炼。
“进来,”Loop教授的声音从开着的门里面传来,“快坐下,免得摔倒了。这个楼梯对于像你这样的年轻人来说有点强人所难了。”
Frank走进了办公室,非常感激地瘫倒在Loop教授桌前的木椅上。他气喘吁吁了好一会儿,Loop教授则静静地看着他。
“不错的办公室!”Frank终于能开口说话了。
“确实不错,不是吗?”Loop教授说,“我等了70年,就为了在这个办公室工作,70年!Iterator教授拒绝退休也是为了这个,而我耐心地等到了这天。你知道Iterator教授宣布退休的那天发生了什么吗?”
Frank摇摇头,还是有些喘不过气,说不出话来。
“有一个年轻又自命不凡的人,也就是Lambda教授,想强占我的办公室!”
“真的?”Frank气喘吁吁地说。
Loop教授耸耸肩:“你应该知道,在警察学院,退休一直都是一件令人激动的事情。因为实行了教龄制度,只有教龄最老的教授可以退休,一旦有人退休,所有人都想找机会搬到更好的办公室去。
“其实,这都是Iterator教授的错。在执教75年后,他终于搬走了,路上还碎碎念着他的一些烦人的学生。但他退休这件事,他只告诉了一个人——Lambda教授,一位只有11年教龄的教授。
“他不顾我们的系统,直接从他寒碜的办公室搬到了顶楼。哈哈!每次有人退休,这种事就会发生!这栋大楼里底层一个办公室的教授直接跑到顶楼去,试图占有那里的办公室。我告诉你,一旦有办公室空出就会这样!
“当我听说Iterator教授的离开时,我直接跑到了顶楼,希望宣告这个办公室是我的。它确实应该是我的,你知道吗,我是唯一一个符合规定的人,我在这里工作了70年。但是有着61年教龄的Babbleton教授听说我跑上去了之后,他也想试试争取这个办公室。他们每次都这样。
“只要有一个办公室空出来了,楼下的两个教授都会跑上去声称这个办公室是自己的。所以在这样的情况下,我和Babbleton教授必须与Lambda教授争抢最好的办公室。
“就这样,Lambda教授、Babbleton教授和我,我们吵了一个多小时,Lambda教授根本没有权利来争夺,大家都心知肚明,但他固执地争了很久。终于只剩我和61年教龄的Babbleton教授在争吵。最后,我赢了,我逼迫只有11年教龄的Lambda去了我的旧办公室,有着61年教龄的Babbleton仍待在他原来那个办公室。
“Lambda教授把他的东西带到了我原来的办公室,但是那个可怜虫发现又有两个教授等着他,他们是我原先办公室楼下的两位教授,正在争取搬上来的机会。
“他们都比Lambda更有资格占用我原先的办公室,他们的教龄分别是40年和30年,这次他们没有吵得太厉害,Variable教授赢了,毕竟他工作了40年。
“不幸的Lambda教授又搬到了楼下,这次,Lambda办公室下一层的两位教授都比他年轻,我觉得他应该感到高兴,因为他赢了,他终于让其他教授吃了闭门羹。
“其实Lambda教授还是很幸运的,”Loop教授解释道,“他本想要占有顶层的办公室,却意外地搬到了办公楼中有较多年轻教授的一边,这使得他最终还是比之前上升了一层。规定只说过楼上的办公室的教授必须要比其楼下办公室的教授教龄更长。所以Lambda教授现在纯粹靠运气赢得了二楼的办公室,但是还有比他更长教龄的教授在一楼呢。”
Frank静静地等老教授把故事讲完,但老教授听起来好像有说不完的话,他试探地问道:“Loop教授,我可不可以占用您一点时间?我想问您一些问题。”
“当然可以,”Loop教授说,“我猜是关于这周的作业问题吧!”
Frank愣了一下,立刻回过神来,“什么?不是,我现在已经不是这里的学生了。”
“你现在还不是吗?那你应该考虑加入警队,这可是一个很光荣的职业。”
“我十年之前就毕业了。”
“是吗?”Loop教授耸了耸肩,“教书教久了,学生们都不记清了。”
“好吧,”Frank说,他绝望地找回刚被打乱的思路,“对了,我想知道关于安保的咒语。”
“哦,我并不教魔法,”Loop教授说,“我教的是巫师犯罪学,这是一门……”
“我上过您的课,”Frank打断道,“我不想知道如何施展咒语,我只想知道有哪些类型的安保咒语,尤其经常会在警局使用的。”
Loop教授的表情突然变得严肃起来。“这是非常敏感的信息,”她说,她的声音变得冰冷,“只有很少一部分人知道。”
“这也是我为什么来这里的原因。”Frank说。
“你到底为什么需要这个信息?”她问。
“我在调查首都警局的盗窃案。”他回答道,心里想:她先是胡言乱语地说了一通故事,现在居然又要盘问我?我时间可不多了。
“我需要看你的警徽。”Loop教授伸出手来。
Frank从他的披风口袋里找出私人侦探的徽章,扔在她的桌上。
“私人侦探?”Loop教授笑了笑,然后她的声音又变得非常强硬,“给我出去。”
“Loop教授……”Frank的声音被插销的上锁声打断。
警用算法导论:堆
节选自Drecker教授讲义
最大堆是基于二叉搜索树的数据结构,它的每个节点与其子节点之间需要时刻维持有序关系。具体来说,堆在存储元素时一定要遵循堆的特性,对于最大堆,树中的任意一个节点的值都要大于(或等于)其下面的所有节点。这种结构允许最大堆高效地支持几个非常重要的操作:(1)找到最大的元素,(2)删除最大的元素,(3)插入任意元素。这三个操作使得堆成为实现优先级队列的理想数据结构。
堆看起来像一棵树,它很容易通过数组来实现,其中数组中的每个元素对应了树中的一个节点,根节点位于索引0处,如下页图所示。子节点索引可以通过父节点的索引计算得到。具体来说就是,索引i处节点的子节点位于索引2×i+1和2×i+2处。因此,索引1处节点的两个子节点分别位于索引(2×1)+1=3和索引(2×1)+2=4处,如下页图所示。
有时为了简单起见,一些堆在实现的时候直接跳过了数组索引0。根节点被放置在索引1处。在这种情况下,索引i处节点的子节点位于索引2×i和2×i+1处,这使得索引计算更为简单。无论哪种方式,都可以便捷地通过父节点的索引值来计算出两个子节点的索引值,也可以通过子节点的索引值计算出父节点的索引值(子节点的索引值除以2后向下取整便可得到其父节点的索引值)。
由于根节点(数组中的第一个元素)总是最大堆中的最大值,因此你可以始终在固定时间内获取该值,而不论数组中还有多少其他元素。这使得用户可以有效地查找优先级队列中的最高值元素。
如果你想添加一个元素或删除最大元素,这个过程会更复杂,需要首先打破堆的特性,然后再逐步恢复堆的特性。
为了添加一个新元素,首先将新的元素添加到数组的最后面(即树底层中的第一个空白处)。如果新添加入节点的值大于其父节点的值,这将破坏堆特性,因此需要将此节点向上移动,直到它不再大于其父节点的值,并重新恢复堆的特性。也就是说,如果新加入节点的值大于其父节点的值,就不断地将该节点的值与其父节点的值进行交换。例如,如果要将60这个数添加到前面的堆中,则首先将它插入底部,然后将其向上移动,进行两次与上一级节点的交换操作。因为第一次在与15交换后,该节点的值仍然大于其新的父节点55,所以还需要再与55交换一次。
删除最大值元素也是类似的。将原来的最大值与数组的最后一个元素交换位置,使原来最后的那个元素成为新的根节点。
接下来删除现在最后的这个元素就可以了(此时原来的最大值已经成为数组的最后一个元素)。虽然现在已经正确地删除了原来的最大值的节点,但这个操作也破坏了堆的特性。
我们需要从新的根节点开始沿树向下调整该节点,以恢复堆的特性。在树的每一层,我们将该节点的值与其子节点进行比较。如果该值小于它的任何一个子节点的值,就需要将该值向下移动,并将两个子节点中值较大的那个子节点与其交换位置,以恢复堆的特性。直到该节点的子节点都比这个值小时,就结束操作。
插入新元素和删除最大元素的操作都需要我们从树顶部逐层调整直至合适的位置,不过最多只需从顶部到底部调整一遍。如果要往堆中增加一倍的节点,只需要在堆的底部增加一层节点即可,所以此时的插入和删除操作依然很快,即使是一个大的堆也会很快。换句话说,虽然堆的节点总数增加了一倍,但堆的层数只增加了一层,插入和删除操作仅比原来多交换一次。此外,由于上述插入和删除操作可以保持树的平衡,所以之后的操作也同样是高效的。