【练习】从一组数字中找出最大的几个，用堆完成

从一组数字中找出最大的几个，例如从n个数字中找出最大的k个，最容易想到的方法是首先对这n个数字进行从小到大的排序，然后选出前面的k个数字就行了，快速排序的平均时间复杂度是O(nlogn)。不过，在有些面试题里面会有这样一个条件： n非常大，以至于无法将这n个数一次性全部读入内存。

这种时候可以用大顶堆来完成这个题目，如果形象的用完全二叉树来想象堆的样子的话，大顶堆中满足“任意一个结点中的值，都大于其子结点中的值”。

在进行实现的时候，也不需要真的用一个树来存放数字，因为是完全二叉树，所以可以很方便的用数组来存放（可以理解为，从树的根结点开始进行广度优先遍历，把遍历的结果以此放在数组中）。只要在这个数组arr中，对于任意一个下标i，满足arr[i*2+1]>=arr[i]和arr[i*2+2]>=arr[i]，则这个数组满足堆的性质。

这个数据中的第一个元素（即arr[0]）对应那棵完全二叉树的根结点中的值，也就是这个完全二叉树中最大的值（大顶堆的根结点中的值）。只要构建好了这样一个包含k个数的大顶堆，接下来就可以依次遍历那n个数，把每一个数同根结点的值进行比较： （1）如果这个数大于大顶堆的根结点，那么这个数就不会是“最小的k个数”之一，不理会这个数； （2）如果这个数等于大顶堆的根结点，虽然这个数是“最小的k个数”之一，但是同样不理会这个数，至于原因，举例来说，我们要找的是最小的3个数，现在大顶堆里面放的是“1,2,2”，现在又读到一个“2”，我们自然不可能把大顶堆里面的“1”换成“2”，用“2”替换“2”等于没换，所以不理会现在读到的这个“2”； （3）如果这个数小于大顶堆的根结点，那么自然大顶堆的根结点不在“最小的k个数”之中，先用这个新来的数替换大顶堆根结点的值，然后再对大顶堆进行调整，使之保持堆的结构。

用堆来完成“用n个数中找出最小的k个数”，时间复杂度为O(nlogk)，时间复杂度比使用排序法稍微好一点，不过最大的优势应该是应对那种“n个数无法一次性全部读入内存”的情况。

至于怎么对大顶堆进行调整，使其保持堆的结构，可以下面的代码，就是replace()方法中的代码。

下面是大顶堆的代码：

下面是测试代码，与使用排序法得到的结果进行比较，观察结果是不是一样来判断代码写对了没有。