微软等数据结构与算法面试100题 第五题
第五题
查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。
分析： 本题目要求计算n个整数的最小的K个，题目没有直接给出复杂度的要求，因此有很多种解法。
比如排序后一次输出等 很多种解法。如果是要求复杂度为klogn的话比较容易想到可以使用分治（递归）算法。
在这里我们使用了两种方法，第一个是比较经典的最小堆算法，第二种就是分治算法。在这里需要说明的一点就是其实这两种算法的本质是一样的，应该都可以算是递归或者分治。只是实现的时候表达出来不一样罢了。
最小堆代码：
[cpp]
#include<iostream>
using namespace std;
class minHeap{
private:
int size;
int * data;
int currentSize;
int Parent(int pos) const;//不会改变成员变量的值
public:
minHeap(int size =100);
~minHeap(){delete [] data;}
bool Insert(const int node);
void siftUp(int pos);
void siftDown();//放入左子树中
int removeMin();
};
int minHeap::Parent(int pos) const
{
return (pos-1)/2;
}
minHeap::minHeap(const int size)
{
if(size<0)
return;
data = new int [size];
currentSize = 0;
}
bool minHeap::Insert(const int node)
{
if(currentSize < size-1)
return false;
else{
data[currentSize] = node;
siftUp(currentSize);
currentSize = currentSize + 1;
return true;
}
}
void minHeap::siftUp(int pos)
{
int temp;
while(pos>0 && data[pos]<data[Parent(pos)])
{
temp = data[pos];
data[pos] = data[Parent(pos)];
data[Parent(pos)] = temp;
pos = Parent(pos);
}
}
void minHeap::siftDown()
{
//默认从0位置开始下降，放进左子树
int temp;
//交换到末位
temp = data[0];
data[0] = data[currentSize-1];
data[currentSize-1] = temp;
currentSize = currentSize -1;
int i = 0;
while(i*2+1<=currentSize-1 && (data[i] > data[2*i+1] || data[i] > data[2*i+2])) //存在左右子树
{
if(i*2+2<=currentSize-1){
//如果左右子树都有
if(data[2*i+1] < data[2*i+2])
{
temp = data[i];
data[i] = data[2*i+1];
data[2*i+1] = temp;
i = 2 * i + 1;
}
else
{
temp = data[i];
data[i] = data[2*i+2];
data[2*i+2] = temp;
i = 2 * i + 2;
}
}
else if (data[i] > data[2*i+1])
{
//如果只有左子树
temp = data[i];
data[i] = data[2*i+1];
data[2*i+1] = temp;
i = 2 * i + 1;
}
else
{
i = 2 * i + 1;
}
}
}
int minHeap::removeMin()
{
int minValue = data[0];
siftDown();
return minValue;
}
int main()
{
minHeap b;
int a[] = { 2, 3, 4, 5, 7, 1, 9};
for(int i = 0; i < sizeof(a)/ sizeof(int) ; i++)
b.Insert(a[i]);
for(int i = 0; i < sizeof(a)/ sizeof(int) ; i++)
cout<<b.removeMin()<<endl;
return 0;
}
递归代码（最大）：
[cpp]
#include<iostream>
using namespace std;
void maxHeap(int *a, int length, int index)
{
int temp;
//没有子树
if(index*2+1>length-1){ }
//只有左子树
else if(index*2+1==length-1)
{
if(a[index*2+1]>a[index]){
temp = a[index*2+1];
a[index*2+1] = a[index];
a[index] = temp;
}
}
else{
//有左右子树，递归
maxHeap(a, length,index*2+1);
int max_left = a[index*2+1];
maxHeap(a, length,index*2+2);
int max_right = a[index*2+2];
if(max_left > max_right){
if(a[index]<max_left){
temp = a[index*2+1];
a[index*2+1] = a[index];
a[index] = temp;
}
}
else{
if(a[index]<max_right){
temp = a[index*2+2];
a[index*2+2] = a[index];
a[index] = temp;
}
}
}
}
int maxHeapDelete(int *a, int length)
{
maxHeap(a,length,0);
int temp;
temp = a[length-1];
a[length-1] = a[0];
a[0]=temp;
return a[length-1];
}
int main(){
int a[8]={1, 2, 6, 4, 3, 7, 9, 11};
//maxHeap(a,8,0);
//cout<<a[0]<<" ";
int temp;
for(int i=0; i<8;i++)
{
cout<<maxHeapDelete(a,8-i)<<" ";
}
//for(int i=0; i<8; i++) cout<<a[i]<<" ";
}
