本文主要是介绍堆排序使用的问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
堆排序使用的方法是一种内部的合并排序,是一种 不稳定的内部排序.不过由于对于top k这一类问题和衍生的问题,即在同时需要处理k个值,所堆排序延伸出的最大堆和最小堆而言优势明显.只会需要O(n lgK).的复杂度.
top K问题
给定一组任意顺序的数，假设有n个。如何尽快地找到它们的前K个最大的数？
首先，既然是找前K个最大的数，那么最直观的办法是，n个数全部都排序，然后挑出前K个最大数。但是这样显然做了一些不必要的事儿。
利用堆这种数据结构
主要步骤如下：
step 1. 随意选出K个数，挑出这K个数的最小的数。这个过程可以用最小堆完成。
step 2. 在剩下的n – K个数中，挑出任意一个数m，和最小堆的堆顶进行比较，如果比最小堆的堆顶大，那么说明此数可以入围前K的队伍，于是将最小堆的堆顶置为当前的数m。
step 3. 调整最小堆。时间复杂度为Olg(K)，由于K是constant(常数级别)，所以时间复杂度可以认为是常数级别。
step 4. 重复进行step 2 ~ step 3，直到剩下的n – K个数完成。进行了n –constant次，时间复杂度为O(n lgK).
问题2：合并k个有序链表
在O(N lgK) 时间内合并K个有序链表， 这里N指的是K个链表中所有的元素个数。
分析：
这是一道非常经典的面试题，在很多大公司的面试题中，此题频繁出现。这题也是算法导论的作业题。
这题的思路如下：
1） 在每一个链表中取出第一个值，然后把它们放在一个大小为K的数组里，然后把这个数组当成heap，然后把该堆建成最小堆。此步骤的时间复杂度为O（K）
2 ）取出堆中的最小值（也是数组的第一个值），然后把该最小值所处的链表的下一个值放在数组的第一个位置。如果链表中有一个已经为空（元素已经都被取出），则改变heap的大小。然后，执行MIN-HEAPIFY操作，此步骤的时间复杂度为O(lg K).
3 ） 不断的重复步骤二，直到所有的链表都为空。
这篇关于堆排序使用的问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
