日常生活中我们总是遇到求解一个数组的最小值或者最大值等问题，这些问题基本上都可以在线性时间复杂度内完成，但是如果需要寻找数组的前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<n;)
{
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<n; i++)
cout<<a[i]<<" ";
cout<<endl;
cout<<"The Second smallest num is: "<<find_second_smallest(a,n)<<endl;
cout<<"The Heap: ";
heap_sort(a,n);
for(int i=0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
cout<<"Input the num: ";
cin>>n;
}
}
上述即为我对堆排序的一些理解，以及堆排序这种思维方式在查询特定条件(第K最小或者第K最大)下的应用，若有什么不对的地方，还请指出，谢谢，欢迎拍砖。