学步园

第五题

查找最小的k个元素

题目：输入n个整数，输出其中最小的k个。

例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

分析： 本题目要求计算n个整数的最小的K个，题目没有直接给出复杂度的要求，因此有很多种解法。

比如排序后一次输出等 很多种解法。如果是要求复杂度为klogn的话比较容易想到可以使用分治（递归）算法。

在这里我们使用了两种方法，第一个是比较经典的最小堆算法，第二种就是分治算法。在这里需要说明的一点就是其实这两种算法的本质是一样的，应该都可以算是递归或者分治。只是实现的时候表达出来不一样罢了。

最小堆代码：

#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;
}

递归代码（最大）：

#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]<<" ";

}