日常生活中我们总是遇到求解一个数组的最小值或者最大值等问题，这些问题基本上都可以在线性时间复杂度内完成，但是如果需要寻找数组的前K个最小值时该怎么做呢？最一般的想法就是将数组排序，然后取出排序后的数组的前k个元素即可，这种算法的时间复杂度也就是排序的时间复杂度为O(NlogN)。但是仔细一想发现，我们没有必要对所有的数进行排序，因为我们只用到了排序后的前K个数，为此可以考虑只找出排序的前K个数即可。这就让我们联想到了堆排序的过程。
堆排序分为两部分，一部分是初始化建堆，另一部分是堆的调整，下面以建立小顶堆为例说明一下堆排序的过程。
堆是一个完整的二叉树，小顶堆即堆顶是此树的最小元素，小顶堆满足父亲节点小于所有的孩子节点。首先将数组看为一个完整二叉树，然后根据堆的性质从第一个非叶子节点开始调整堆。
使用递归的方法对每个节点进行调整，直到调整到根节点为止。
堆建完之后，堆顶的元素即为数组的最小值，然后将其取出，将最后一位叶子元素放到堆顶，接着继续调整堆，然后再取出堆顶元素，如此重复上述步骤K次，即可得到数组中前K个最小元素。
本文以K=2为例子实现了上述算法
建堆：
void Create_Heap(int* a, const int n)
{
?for(int i=(n-1)/2; i>=0; i--)
?{
? Exchange_Node(a,n,i);
?}
}
调整堆：
void Adjust_Heap(int* a, const int n, const int point)
{
?for(int j=point; 2*j+1?{
? if(j*2+2 < n)
? {
? ?int temp;
? ?if(a[j] < a[2*j+1] && a[j] < a[2*j+2])
? ? break;
? ?else if(a[2*j+1] > a[2*j+2])
? ?{
? ? temp = 2*j+2;
? ?}
? ?else
? ?{
? ? temp = 2*j+1;
? ?}
? ?int temp_a = a[j];
? ?a[j] = a[temp];
? ?a[temp] = temp_a;
? ?j = temp;
? ?
? }
? else
? {
? ?if(a[2*j+1] < a[j])
? ?{
? ? int temp = a[j];
? ? a[j] = a[2*j+1];
? ? a[2*j+1] = temp;
? ? j = 2*j+1;
? ?}
? ?break;
? }
?}
}
找到前2个最小的数
int find_second_smallest(int* a, int n)
{
?Create_Heap(a,n);
?int temp;
?temp = a[0];
?a[0] = a[n-1];
?a[n-1] = temp;
?Adjust_Heap(a,n-1,0);
?return a[0];
}
上述算法的性能分析：
假设总共有n=2^(k+1)个节点，则完全二叉树有k+1层，从第k-1层开始调整，其中第k-1层有2^(k-1)个节点，每个节点需要调整1次(因为只用在第k-1层到第k层之间调整)，然后调整第k-2层，其中k-2层有2^(k-2)个节点，每个节点需要调整2次(从第k-2层调整到第k层)，……，最后调整根节点(0层元素)，有2^(0)个节点，每个节点需要调整k次，综上所述在建堆的过程中总共需要调整的次数为2^(k-1)+2^(k-2)*2+2^(k-3)*3+……+2^(0)*k=2^(k+1)-2-k，其中k=logN，为此总的调整时间为O(N-2)，之后每次取出一个值只需要调整一次堆，所需时间即为堆的深度，所以查找第二小的元素所需时间为O(N + logN - 2)。
上述分析的基础上我还实现了堆排序，代码如下所示
void heap_sort(int* a, int n)
{
?Create_Heap(a,n);
?for(int i=n-1; i>0; i--)
?{
? int temp;
? temp = a[0];
? a[0] = a[i];
? a[i] = temp;
? Adjust_Heap(a,i,0);
?}
}
测试代码
void main()
{
?int n;
?cout<<"Input the num: ";
?cin>>n;
?while(n>0)
?{
? int* a = new int[n];
? for(int i=n; i>0; i--)
? ?a[n-i] = i;
? for(int i=0; i? ?cout<? cout<? cout<<"The Second smallest num is: "<? cout<<"The Heap: ";
? heap_sort(a,n);
? for(int i=0; i? ?cout<? cout<? cout<<"Input the num: ";
? cin>>n;
?}
}
上述即为我对堆排序的一些理解，以及堆排序这种思维方式在查询特定条件(第K最小或者第K最大)下的应用，若有什么不对的地方，还请指出，谢谢，欢迎拍砖。