现在我们来分析一下堆排序的时间复杂度、空间复杂度以及稳定性。整个堆排序的过程中，只需要个别的临时存储空间，所以堆排序是原地排序算法。堆排序包括建堆和排序两个操作，建堆的时间复杂度是O(n)，排序过程时间复杂度是O(nlogN)。所以，堆排序的整个时间复杂度是O(nlogN)。因为在排序的过程中，存在将堆的最后一个节点跟堆顶互换的操作，所以有可能会改变值相同数据的原始相对顺序，所以堆排序不是稳定的排序算法。
四、堆的应用下面我们来说一下堆的几个非常重要的应用。
1.优先级队列优先级队列，顾名思义，它首先是一个队列。队列的最大特性就是先进先出。但是，在优先级队列中，出队的顺序不是按照先进先出，而是按照优先级来，优先级高的先出队。
如何实现一个优先级队列呢？其实有很多方法，不过使用堆来实现是最直接、最高效的。因为堆和优先级队列非常相似。一个堆就可以看做是一个优先级队列。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出最高优先级的元素，就相当于取出堆顶元素。我们来看一下下面这样一个应用场景。
假如我们有100个小文件，每个文件的大小是100MB。每个文件中存储的都是有序的字符串。我们希望将这些小文件合并成一个有序大文件。这里就会用到优先级队列。 我们将从100个小文件中，各取出一个字符串，然后我们建立小顶堆，那堆顶的元素，也就是优先级队列的队首元素，也就是最小的字符串。我们将这个字符串放到大文件中，并将其从堆中删除。然后再从小文件中取出下一个字符串放入堆中。循环此过程，就可以将100个小文件的数据依次放入到大文件中。
2.利用堆求topK我们可以把求topk的问题抽象成2类。一类是针对静态数据集合，也就是说数据集合事先确定，不会再变。另一类是针对动态数据集合，也就是说数据集合事先不确定，有数据动态地加入到集合中。 针对静态数据集合，如何在包含n个数据的数组中，查找前K大数据呢?我们可以维护一个大小为k的小顶堆，顺序遍历数组，从数组中取出数据和堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，我们就不做处理，继续遍历数组。这样等数组中的数据都遍历完成之后，堆中的数据就是前K大数据了。 针对动态数据求得topK，也就是实时topK。怎么理解呢？我举个例子。一个数据集合中有两个操作，一个是添加数据，另一个就是询问当前的前K大数据。 如果每次询问前k大数据时，我们都基于当前的数据重新计算的话，那时间复杂度就是O(nlogN)，n表示当前数据的大小。实际上我们可以一直维护一个k大小的小顶堆，当有数据要添加到集合中时，我们就拿它与堆顶元素做对比。如果比堆顶元素大，我们把堆顶元素删除，并将这个元素插入到堆中；如果比堆顶元素小，我们则不做处理。这样，不论何时需要查询前K大数据，我们都可以立刻返回给它。
更多硬核知识，请关注公众号“”。