第五題
查找最小的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]<<" ";
}
