2.6.2　最大最小堆

除了快速排序，堆排序也相对比较常用。这里特别介绍最大最小堆，它其实就是堆排序的优先级队列。堆排序本身是由完全二叉树这样的结构支撑的，普通堆排序比快速排序更低效，但堆排序中的最大最小堆的优先级队列非常有用，即只关注最大值或最小值，在不断增加和删除根节点元素的情况下仍可获取最大值或最小值。优先级队列完成排序后，数据堆就成了一个头顶着一个最大值或最小值的数据结构，这种数据结构更有利于获取根节点的最大最小值节点，在后面的程序逻辑中，当需要插入新元素、修改旧元素及推出最大最小值时，效率比较高。优先级队列在实时获取最大最小值时高效的特点，导致它在寻路系统的A星算法中特别有用，因此最大最小堆排序常用于A星算法。

由于堆排序是一种完全二叉树结构，所以这种结构可以用一维数组表示，这样会让效率更高，因为内存是连续的。使用一维数组表示二叉树时，通常是以完全二叉树形式表示每个节点及其子节点，每个节点一一对应数组上的索引规则，即如果i为节点索引，i2和i2+1就是它的两个子节点，而索引i的父节点位置可以用i/2来表示，数组中的任何节点都应遵循这种规则。以此类推到子节点，即(i2)2和(i2)2+1就是i2这个索引的两个子节点，所有子节点自身的索引直接除以2就是父节点的索引，即i2和i×2+1各除以2后取整就是它们的父节点索引i。

最大最小堆的优先级队列的操作分为插入元素、返回最大或最小值、返回并删除最大最小值、查找并修改某个元素，其中关键的算法在于插入新元素和删除最大最小元素。其基本思想是，利用完全二叉树的特性，将新元素放入二叉树的叶子节点上，然后比较它与父节点的大小，如果它比父节点大（最小堆的情况），则结束，否则就与父节点交换，继续比较，直到没有父节点或者父节点比它小为止。删除根节点则反过来，把最后一个叶子节点放入根节点，然后找到这个新根节点的实际位置，即比较它与两个子节点的大小，如果比它们小（最小堆的情况），则结束，否则取最小值（最小堆的情况）替换节点位置，然后再继续向下比较和替换，直到停止或者替换到叶子节点时再没有子节点可比较为止，这样就算完成了操作。

图2-3和图2-4能很好地理解插入与删除的步骤。

图2-3　插入时的堆排序步骤

图2-4　删除根节点步骤

图2-3为插入时的堆排序步骤，在此过程中，不断与父节点比较并交换，直到到达根节点或者无法交换为止。图2-4为删除根节点的情况，此过程中把根节点与叶子节点交换后，叶子节点再从根部不断比较并下移到应有的位置。