https://www.douban.com/note/275544555/
题目：给出N个无序的数，然后找出其中最大的k个数
解题思路：
首先测试数据有可能会有一亿个数，数据量特别的大，数据库不可能存储这么多的数据。如果直接sort排序，NlogN时间复杂度实在是太高，大于10^9。我们可以考虑对数据进行分块读取，每次读取的数据块大小应大于k。
不如先假设第一次读取的数据块前k个数最大，然后把k个数建成最小二叉堆。然后从第k+1个数开始，每个数都与堆顶的数值进行比较，如果数字i大于堆顶则把堆顶的元素的元素替换成i，再调整一次堆。最后读取完数据之后，这个二叉堆里面的元素就是从小到大排序好的最大k个数。
时间复杂度：O(NlogK)
空间复杂度：O(K)
证明过程:
为什么求最大的k个用的不是最大堆，而是最小堆？最大堆堆顶的元素是最大的，往下的子树越来越小，把N个数建成最大堆，那么堆顶往下的k个数就是最大的k个数。但是时间复杂度O(NlogN)和空间复杂度O(N)太高！
排序时间复杂度很高，是因为进行了很多没有用的判断，我们只需要取最大的k个数，而排序则把N个数都从小到大排序好了。建立一个k个数的最小堆，假设堆里面的元素是最大的，当然只是假设。如果从M+1到N这些数只要有数大于最小堆堆顶的数，那么假设就不成立，堆顶那个数就不符合，自然把它去掉，把新的数加进来，再重新调整堆，使得堆顶的元素最小。
为什么要用最小堆呢？因为每次查找这k个数里面的最小的那个数就是堆顶，时间复杂度是O（1）。如果直接用数组来存储这k个数，虽然查找的时间复杂度是logN，但是当把这个数插入数组的时候，数组比它小其他元素还需要往前平移，所以时间复杂度远远大于logN。由于每次调整堆的时间复杂度是logN。所以最小堆的做法的时间复杂度是
O(NlogK)，而空间复杂度只有O(K)。
代码1 C++的STL库优先队列实现二叉堆：
#include
#include
#include
#include
#include
using namespace std;
struct cmp{
bool operator ()(int a,int b)
{
return a>b;
}
};
#define MAX 11000
int a[MAX];
using namespace std;
priority_queue,cmp>q;
int main()
{
int n,i,k,m,top;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&k);
if(i<=m) //前m个数入 队列
{
q.push(k);
if(i==m) //纪录前m个数中最小的数
top=q.top();
}
else
{
if(k>top) //如果新加入的数大于队列中最小的数则出队
{
q.pop();
q.push(k);
top=q.top();
}
}
}
k=0;
while(!q.empty()) //这样处理是为了最后一个数打印时没有空格
{
a[k++]=q.top();
q.pop();
}
for(i=0;i
{
printf("%d",a[i]);
if(i==k-1)
printf("\n");
else
printf(" ");
}
return 0;
}
代码2 (数组实现堆)：
#include
#define MAX 10001
int a[MAX];
void HeapAdjust(int R[],int s,int t) //筛选函数1
{
int i,j,temp;
temp=R[s];
i=s;
for(j=2*i;j<=t;j=2*j)
{
if(j
j++;
if(temp>R[j]) break;
R[i]=R[j];
i=j;
}
R[i]=temp;
}
void HeapSort(int R[],int n) //堆排
{
int i;
for(i=n/2;i>0;i--)
{
HeapAdjust(R,i,n);
}
for(i=n;i>1;i--)
{
R[1]^=R[i];
R[i]^=R[1];
R[1]^=R[i];
HeapAdjust(R,1,i-1);
}
}
void HeapAdjust2(int R[],int s,int t) //筛选函数2
{
int i,j,temp;
temp=R[s];
i=s;
for(j=2*i;j<=t;j=2*j)
{
if(jR[j+1])
j++;
if(temp
R[i]=R[j];
i=j;
}
R[i]=temp;
}
int main()
{
int i,k,n,m;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d",&a[i]);
}
HeapSort(a,m);
for(i=m+1;i<=n;i++)
{
scanf("%d",&k);
if(k>a[1]) //新元素大于堆中最小元素则加入堆
{
a[1]=k;
HeapAdjust2(a,1,m); //从根节点开始重新筛选一次
}
}
HeapSort(a,m);
for(i=1;i<=m;i++)
{
printf("%d",a[i]);
if(i==m)
printf("\n");
else
printf(" ");
}
return 0;
}
网友评论