算法练习：寻找最小的k个数

参考July的文章：http://blog.csdn.net/v_JULY_v/article/details/6370650

寻找最小的k个数
题目描述：查找最小的k个元素
题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

总体思路：

取n个数字的前k个数字构建大根堆，设根顶元素为kmax，

从n-k+1开始遍历剩余的n-k个元素，取出每一个元素和大根堆根元素进行比较，如果kmax>遍历到的元素值，则kmax=遍历到的元素值，并更新大根堆。

算法时间复杂度分析：TODO

C++代码：

#include <iostream>

#include <assert.h>

using namespace std;

//调整根元素序号为index的子树

void MaxHeapAdjust(int arr[], int index, int len)

{

    int largeIndex = index;

    int leftChildIndex = index * ;

    if(leftChildIndex <= len && arr[leftChildIndex] > arr[index])

    {

        largeIndex = leftChildIndex;

    }

    int rightChildIndex = index *  + ;

    if(rightChildIndex <= len && arr[rightChildIndex] > arr[index] && arr[leftChildIndex] < arr[rightChildIndex])

    {

        largeIndex = rightChildIndex;

    }

    if(largeIndex != index)

    {

        int tmp = arr[index];

        arr[index] = arr[largeIndex];

        arr[largeIndex] = tmp;

        MaxHeapAdjust(arr, largeIndex, len);

    }

}

void MaxHeapBuild(int arr[], int len)

{

    for(int i=len/; i>=; i--)

    {

        MaxHeapAdjust(arr, i, len);

    }

}

int main()

{

    //int a[] = {1, 2, 3, 4, 5, 6, 7, 8};

    int a[] = {, , , , , , , };

    //从n个元素中查找出最小的k个元素

    const int n = ;

    const int k = ;

    //构建k个元素的大根堆

    int maxheap[k+];//因为堆元素的序号从1开始，数组的序号从0开始，这里添加一个无意义的首元素maxheap[0]

    for(int i=; i<=k; i++)

    {

        maxheap[i] = a[i-];

    }

    MaxHeapBuild(maxheap, k);

    cout << "构建k个元素的大根堆" << endl;

    for(int i=;i<=k;i++)

        cout << maxheap[i] << " ";

    cout << endl;

    //遍历剩下的n-k个元素，与大根堆的根元素进行判断处理

    for(int i=n-k; i<n; i++)

    {

        if(maxheap[] > a[i])

        {

            maxheap[] = a[i];

            MaxHeapAdjust(maxheap, , k);

        }

    }

    cout << "查找出的最小的k个元素为" << endl;

    for(int i=; i<=k; i++)

        cout << maxheap[i] << " ";

    cout << endl;

    cin.get();

    cin.get();

    return ;

}

算法练习：寻找最小的k个数的相关教程结束。