预计阅读本页时间：-
堆排序
在数组A[0,n)中寻找最大的元素最少需要n-1次比较，但是我们希望能够最少化直接比较的元素。在体育领域，通过锦标赛在n个队伍中寻找“最好的”队伍，而不是强制最终的优胜者和所有其他的n-1支队伍比赛。NCAA冠军锦标赛是美国最流行的篮球赛事之一，这项赛事有64支学校的代表队参加，角逐冠军头衔。最终的冠军队伍在进入决赛之前会和5支队伍进行比赛，所以它需要赢得6场比赛。非常巧合的是log(64)=6。堆排序则表明了如何应用这种行为来排序元素，其伪代码描述如图4-14所示。
一个堆就是一棵二叉树，它具有以下两个性质：
外形的性质
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
如果深度k-1存在2k-1个节点，那么深度k（k＞0）上存在叶子节点。另外，在一个部分填充的深度级上，节点是“从左到右”添加的。
堆的性质
树中每一个节点的值都大于或者等于任意一个子节点的值（如果有的话）。
图4-15标记为a的堆就满足这些性质。二叉树的根节点的值必须是树中最大的，但是，注意到最小的元素可以是任何一个叶子节点。虽然二叉树的有序信息受限于这样一个事实：一个节点大于任意一个子节点。堆排序表明了如何利用这个外形的性质来高效地排序元素。
给定严格满足外形性质的一个结构，堆能够存储在一个数组A中，而不损失任何结构信息。图4-15b描绘了给堆中每一个节点都赋予一个整数值标签。根节点被标记为0。对于每一个标记为i的节点，其左子节点（存在的话）被标记为2*i+1；其右子节点（如果存在的话）被标记为2*i+2。类似地，对于一个标记为i的非根节点，其父节点被标记为
(i-1)/2」。使用这个标记，我们能够将堆存储在一个数组中，节点存储在数组中的位置就是其标签。图4-15 c表示了存储在数组中的对。A中元素的顺序从左至右能够被简单地看做节点被发现的深度。
堆排序在排序数组的时候，首先会将数组中的元素放到堆中“合适的位置”。事实上，图4-15所示的堆是在一个已经有序的数组上执行build Heap（图4-14有这个函数的伪代码）得到的结果。buildHeap执行的过程如图4-16所示。如果A[i]的两个子节点A[2*i+1]和A[2*i+2]至少有一个比A[i]大，heapify(A，i，n)通过交换A[i]和两个子节点中较大的来更新A。如果交换过程发生了，heapify递归地检查其孙子节点来正确地维护A的堆性质。你能够看到，在结果堆中，最终大数会被“抬升”（意思是它们会和左边的较小元素交换）。图4-16灰色的方格描述了heapify在第9行被交换的元素。
在排序一个大小为n的数组A，堆排序将其切分成两个相异的子数组，A[0,m)和A[m,n)，分别表示一个大小为m的堆和一个有n-m个元素的有序子数组。随着i从n-1迭代到1，堆排序交换堆中的最大元素（位置是A[0])和A[i]，使子数组A[i,n)的大小不断增长；然后堆排序执行heapify重构A[0,i)使其成为一个有效堆（图4-14描述了伪代码）。结果非空子数组A[i,n)将会有序，因为堆中的最大的元素保证比这个有序子数组中的任何一个元素都要小。
使用环境
堆排序不是一个稳定的排序。因为它非常频繁地移动元素，所以它不能使用基于值的数据。
