27 警察学院中的“堆”（第2/3页）

“不幸的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交换一次。