转载至：http://www.cnblogs.com/ywl925/p/3794852.html
假定有20个有序数组，每个数组有500个数字，降序排列，数字类型32位uint数值，现在需要取出这10000个数字中最大的500个，怎么做？
解决方法
这里其实有很多解决方法，笨拙的或者巧妙的。这里介绍一个非常不错的方法，使用最大堆堆排序：
1. 建立大顶堆，维度为数组的个数，这里为20（第一次 插入的是每个数组中最大的值，即第一个元素）。
2. 删除最大堆堆顶，保存到数组或者栈中，然后向最大堆插入删除的元素所在数组的下一个元素。
3. 重复第1,2个步骤，直到删除个数为最大的K个数，这里为500.
代码：
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
#define ROWS 20
#define COLS 500
int data[ROWS][COLS];
void CreateData()
{
for(
int i=
0; i<ROWS; i++
)
{
for(
int j=
0; j<COLS;j++
)
{
data[i][j] = rand();
//生成随机元素
}
}
for(
int i=
0; i<ROWS; i++
)
sort(data[i],data[i]+COLS, greater<
int>());
//对每一行降序排列
}
struct Node
{
int *p;
//指向某个列，因为要放入优先队列中，所以要比较大小，就用结构体封装了下
bool operator<(
const struct Node &node)
const
{
return *p < *
node.p;
}
};
void OutMinData(
int k)
{
struct Node arr[ROWS];
for(
int i=
0; i<ROWS;i++
)
{
arr[i].p = data[i];
//初始化指针指向各行的首位
}
priority_queue<Node > queue( arr, arr+ROWS );
//使用优先队列，默认是大堆
for(
int i=
0; i<k&&i<COLS; i++)
//算法核心就是这个循环
{
Node temp = queue.top();
//取出队列中最大的元素
cout << *temp.p <<
" " <<
endl;
queue.pop(); //从队列里删除
temp.p++;
//对应行的指针后移
queue.push( temp );
//这里面有log（ROWS）次操作，所以算法的总复杂度为O（klog（20））
}
}
int main()
{
CreateData(); //生成数据
int k=
500;
OutMinData( k ); //输出k个元素，这里k不要大于列数COL，可以改进，去掉这个限制，不过会让程序不好懂，就没加
return 0;
}
题外话：
上面的是有序数组，但是如果是无序数组呢，可以建立维度为K（这里为500）的最小堆，然后每次删除最小堆的堆顶，直到遍历完所有的数，剩下的就是所求的最大K个数。
我们向堆插入数值时，首先我们先在堆的尾部插入该值，然后再根据大小关系不断的提升它的位置
删除堆的最小值时，首先把堆的最后一个节点复制到根节点上，然后删除最后一个节点。之后我们根据大小关系不断和交换位置，使其满足堆的定义。
堆的这两种操作所用的时间，和树的深度成正比。我们不难发现堆的时间复杂度为O(log n).
