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

删除最大值元素也是类似的。将原来的最大值与数组的最后一个元素交换位置，使原来最后的那个元素成为新的根节点。

接下来删除现在最后的这个元素就可以了（此时原来的最大值已经成为数组的最后一个元素）。虽然现在已经正确地删除了原来的最大值的节点，但这个操作也破坏了堆的特性。

我们需要从新的根节点开始沿树向下调整该节点，以恢复堆的特性。在树的每一层，我们将该节点的值与其子节点进行比较。如果该值小于它的任何一个子节点的值，就需要将该值向下移动，并将两个子节点中值较大的那个子节点与其交换位置，以恢复堆的特性。直到该节点的子节点都比这个值小时，就结束操作。

插入新元素和删除最大元素的操作都需要我们从树顶部逐层调整直至合适的位置，不过最多只需从顶部到底部调整一遍。如果要往堆中增加一倍的节点，只需要在堆的底部增加一层节点即可，所以此时的插入和删除操作依然很快，即使是一个大的堆也会很快。换句话说，虽然堆的节点总数增加了一倍，但堆的层数只增加了一层，插入和删除操作仅比原来多交换一次。此外，由于上述插入和删除操作可以保持树的平衡，所以之后的操作也同样是高效的。