本文共 2739 字，大约阅读时间需要 9 分钟。

堆

1. 堆是一个完全二叉树，树中每一个节点的值，都大于等于，或者小于等于其子树中每个节点的值；

2. 堆分为大顶堆和小顶堆，因为是完全二叉树，所以可以很方便的使用数组存储，数组下标是按层依次递增；

   

3. 堆的插入操作，首先将新插入节点放在数组末尾，即完全二叉树的最后一个叶子节点，并从下往上，进行比较，查看是否满足大于等于 ( 小于等于 ) 父节点的条件，如果不满足，与之交换，并向上循环判断，直到满足条件，没有交换元素，或者到达根节点；

4. 删除堆顶元素，堆顶，即为最大元素或者最小元素，以大顶堆为例，堆顶是最大元素，第二大元素必定在堆顶的左右子节点中，所以将左右节点中较大的放入堆顶，并逐步向下，比较左右节点，大的往上移动，直到叶子节点为止，不过这种方案，最后得到并不是完全二叉树；

5. 删除堆顶元素，可以这样改进，移除堆顶元素后，将堆的最后一个元素，放置在堆顶，然后从上往下，根据堆的要求，进行元素交换，这样最终还是完全二叉树；

6. 堆的插入操作，删除堆顶元素操作，时间复杂度都是 O( logn )，堆的每一层只需要比较，交换元素即可，所以和数的高度相关；

堆排序

1. 给定一个数组，要求对数组元素排序，可以使用堆排序

2. 首先需要建堆，一种方案是当中起始堆只有下标为 1 的一个元素，其他元素都是将要新插入的元素，依次执行插入操作，从下往上进行比较，交换；第二种方案，是从第一个非叶子节点开始，从上往下进行堆化，比较和交换元素；

数组中，第一个非叶子节点，是下标为 n/2 的元素，因为大于 n/2 下标的元素，其子节点将超出数组长度，即没有子节点	因此可以从 n/2 到下标为 1 的元素，从上往下进行堆化，如此就完成了建堆	每一个节点，进行堆化的时间复杂度都是 logh，h是高度	最后得到建堆的时间复杂度是 o( n )

3. 建堆完成后，就构成了一个大顶堆，然后需要进行排序，就可以每次将堆顶元素和最后一个元素交换，然后从上往下进行堆化，就形成了最后一个元素是最大元素，剩余 n -1 的元素是新的大顶堆，然后依次进行该步骤，最后就完成了排序，整个排序过程的时间复杂度是 o( nlogn )；

4. 堆排序就此完成，空间复杂度是 o( 1 )，额外占用常数级空间，时间复杂度是 o( n + nlogn)，即为 o( nlogn )，并且堆排序不是一个稳定排序，因为每次排序都涉及堆顶和最后一个元素交换，可能破坏了相等元素的顺序性；

5. 与快速排序相比，堆排序的交换次数往往要多于快速排序，因为快速排序会利用到原始数据的有序度，而堆排序，开始建堆，就可能破坏了有序度，所以堆排序没有快速排序应用广；

堆的应用

1. 用堆结构实现优先级队列，首先是一个队列，但出队顺序是按照优先级，优先级高的先出队，在 Java 中即是 ProrityQueue；

向优先级队列中插入一个元素，就是往堆中插入一个元素	从优先级队列中获取一个元素，就是获取和删除堆顶元素；

2. 算法操作，合并 100 个小文件，到一个大文件，小文件内部有序，要求大文件有序；

执行过程，和归并排序类似，每个小文件，有一个指针，每个指针从一个小文件取出一条数据，总共 100 条数据，然后选择		最小的一条，放入新文件中，然后将最小数据的文件指针后移一位	每次从100条数据，选择最小的，如果每次都是顺序比较，效率低，可以构造一个最小堆，这样每次取走栈顶元素，并将新元素  		放置栈顶，从上向下堆化，这样每次选择时间复杂度就是 o( logn ),而顺序比较就是 o( n ),且该操作要进行很多次

3. 实现高效的定时器，假设一个任务列表，记录了任务和需要执行的时间，用一个定时器来扫描和执行；

简单的办法是，通过定时器，每隔一秒去扫描该任务列表，找到需要执行的任务，触发执行		这种方案每秒都要触发扫描操作，且需要遍历整个任务列表，效率低下	为此可以利用最小堆，将任务按时间存储在最小堆，那么堆顶就是最先需要执行的任务，每次从堆顶元素取出任务触发，并且将		下一个堆顶元素的任务，与当前时间比较，设置下次定时器的触发时间，这种方式避免了每秒扫描，而是任务要执行时直		接获取，并且不用扫描任务列表，直接获取堆顶任务即可

4. 获取热门 top K 搜索关键字的应用，即要从一个大集合中找到前 K 大元素，

如果关键字集合是静态数据，可以维护一个 k 大小的小顶堆，然后遍历全部数据，如果比堆顶元素大，则将新元素替换堆顶元		素，如果小，继续遍历	这种方式，每次入堆，执行堆化的时间复杂度 o(logk)，最坏情况下所有元素入堆一次，总的时间复杂度 o(nlogk)	如果关键字集合是动态数据，可以一直维护一个基于当前数据的 k 大小的小顶堆，这样每次插入新数据，都与堆顶元素进行比		较，同样比他大，替换堆顶元素，这样就一直维护了一个实时的 top k

3. 求一组数据的中位数，即一组数据排序后，第(1+n/2) 数据，或者第 n/2 和 (1+n/2) 的数据；

如果是静态数据集合，对其排序，直接取出中位数即可	如果是动态数据集合，每次都要维护一个有序集合，比较耗时，可以先将数据排序，分成两部分，前半部分构造一个大顶堆，后			半部分，构造一个小顶堆，那么大顶堆的堆顶元素就是中位数		对于新插入的元素，如果小于大顶堆的堆顶，将其插入到大顶堆，否则插入小顶堆，并且如果不满足偶数个数据，大顶堆数				据个数是 n/2，奇数个数据，大顶堆数据个数是 1+n/2，就从一个堆的堆顶，移动数据到另一个堆中

4. 中位数引申，求一组数据的百分比数据，如求一个接口的 99% 响应时间，即将这个接口的所有响应时间排序，获取第 99% 位置的值，为此同样将接口响应时间排序，维护两个堆，一个大顶堆保存 99%的数据，另一个小顶堆保存 1%的数据，新插入数据，和维护两个堆数据比例的方法，和之前求中位数一致；

5. 使用 1 G 内存，求 10 亿搜索关键字中的 top 10；

整体思路是：首先要统计 10 亿个关键字中，每个关键字的出现次数，可以使用散列表，或者平衡二叉树这种方便查找，插入的		数据结构，然后在不重复关键字，包含关键字次数的集合中，构造一个 10 数据大小的小顶堆，遍历集合元素，和堆顶元素			进行比较，比堆顶元素大，替换堆顶元素，小于堆顶元素，继续下一个循环	这里，统计关键字次数，可以使用散列表，但 1 g内存，能存储数据有限，所以可以先将 10 亿数据分为 10 份，划分方式要		根据哈希算法对 10 求余，这样保证相同数据被分在一起，统计次数准确，然后对每一份数据，求出 top 10		最后，对 10 个 top 10，得到最终的 top 10

转载地址：http://gsfin.baihongyu.com/