<strong>题目要求：</strong>5.查找最小的k 个元素题目：输入n 个整数，输出其中最小的k 个。例如输入1，2，3，4，5，6，7 和8 这8 个数字，则最小的4 个数字为1，2，3 和4。</p><p class="p1"></p><p class="p1">题目分析：</p><p class="p1"></p><p class="p1">粗看此题想到此题是考察排序算法，但是观察一下就会发现。由于题目中只是要求输出最小的k个数，并没有求出所有元素的顺序。由于考虑时间复杂度和空间复杂度尽可能的小。那么想想看看有没有线性的算法解决这个问题。首先想到的是取任意k个数构建一个最大堆，然后选取后面的n-k个数与最大堆进行比较，若比最大值的元素值小，那么对最大堆进行调整。OK想一下这种方法的时间复杂度。用调整法构建一个k个元素的最大堆需要O(k)的时间复杂度，假设后序n-k个元素在最坏情况都比最大堆的最大元素小，那么时间复杂度是：O(n-k + (n-k)logk)经过计算这种方法总的时间复杂度是O(nlogk)。这样与我的原目标不想符不过这也不失是一个好办法。这里主要是为了练习实现一下最大堆。</p><p class="p1"></p><p class="p1">实现的一个最大堆：最大堆的头文件的定义：</p><pre name="code" class="cpp">//
// maxHeap.h
// 100-alg-tests
//
// Created by bobkentt on 15-3-31.
// Copyright (c) 2015年 kedong. All rights reserved.
//
#ifndef ___00_alg_tests__maxHeap__
#define ___00_alg_tests__maxHeap__
#include <vector>
#include <stdio.h>
/* 为加深对最大堆的理解本程序实现一个最大堆 */
typedef int valueType;
#define CREATE_BY_INSERT true
#define CREATE_BY_ADJUST false
class maxHeap {
/// 存储堆的数据
std::vector<valueType> &m_data;
/// 用调整法构造最大堆
/// 序列对应一个完全二叉树；从最后一个分支结点（n div 2）开始，到根（1）为止
/// 依次对每个分支结点进行调整（下沉），以便形成以每个分支结点为根的堆，当最后
/// 对树根结点进行调整后，整个树就变成了一个堆。
/// 时间复杂度O(n)
void createByAdjust();
/// 用插入法构造最大堆
/// 从空堆开始，依次插入每一个结点，直到所有的结点全部插入到堆为止。
/// 时间复杂度O（n*lgn）
void createByInsert();
void heapUp(unsigned long index);
void heapDown(unsigned long index);
valueType getValue(unsigned long index);
bool setValue(unsigned long index,valueType value);
/// 禁止复制
maxHeap(const maxHeap&);
const maxHeap& operator =(const maxHeap&);
void adjust(unsigned long index,unsigned long size);
public:
maxHeap(std::vector<valueType> &data, bool type) : m_data(data) {
#if 0
if (true == type) {
createByInsert();
} else {
createByAdjust();
}
#endif
createByAdjust();
}
~maxHeap() { };
/// 插入一个值到最大堆
bool insert(valueType value);
/// 删除位置在index处的元素
bool remove(int index);
/// 对最大堆进行排序
bool sort();
void adjust();
valueType getMaxValue();
void printMaxHeap();
};
bool maxHeap_test();
#endif /* defined(___00_alg_tests__maxHeap__) */
最大堆的实现源码：
// maxHeap.cpp
// 100-alg-tests
//
// Created by bobkentt on 15-3-31.
// Copyright (c) 2015年 kedong. All rights reserved.
//
#include <iostream>
#include "maxHeap.h"
using namespace std;
void maxHeap::createByAdjust() {
adjust();
return;
}
void maxHeap::createByInsert() {
return;
}
bool maxHeap::insert(valueType value) {
/* 数组下标为0的位置不放元素 */
if (0 == m_data.size()) {
m_data.push_back(0);
}
m_data.push_back(value);
heapUp(m_data.size() - 1);
return true;
}
/* 删除一个元素的步骤：
* 1.把最后位置元素的值赋给待删除元素的值；
* 2.对替换的元素执行下沉操作；
* 3.删除最后一个元素。
*/
bool maxHeap::remove(int index) {
m_data[index] = m_data[m_data.size() - 1];
heapDown(index);
m_data.pop_back();
return true;
}
bool maxHeap::sort() {
return true;
}
/* 上升，让插入的数和父节点的数值比较，当大于父节点的时候就和父节点的值相交换. */
void maxHeap::heapUp(unsigned long index) {
#ifdef RECURSION_STYLE
/* 递归实现 */
/* index=1时为根结点 */
if (index > 1) {
/* 获取当前结点的父结点 */
unsigned long parent = index / 2;
valueType parentValue = getValue(parent);
valueType value = getValue(index);
/* swap parent value */
if (parentValue < value) {
setValue(index,parrentValue);
setValue(parent, value);
heapUp(parent);
}
}
#else
/* 非递归实现*/
for (; index > 1; index = index/2) {
/* 获取当前结点的父结点 */
unsigned long parent = index / 2;
valueType parrentValue = getValue(parent);
valueType value = getValue(index);
/* swap parent value */
if (parrentValue < value) {
setValue(index,parrentValue);
setValue(parent, value);
}
}
#endif
return;
}
void maxHeap::heapDown(unsigned long index) {
unsigned long child = 0;
valueType tmp = m_data[index];
unsigned long n = m_data.size() - 2;
/* 递归的方式未实现. */
/* 非递归实现 */
for (; 2 * index <= n ; index = child) {
/* 获得左儿子的位置 */
child = index * 2;
if (child == n) {
/* 如果只有左儿子 */
child = index * 2;
} else if(m_data[child] < m_data[child + 1]) {
/* 如果右儿子的值比左儿子的值大 */
child++;
}
if (m_data[child] > tmp) {
setValue(index, m_data[child]);
setValue(child, tmp);
} else {
break;
}
}
return;
}
void maxHeap::adjust() {
for (unsigned long i = m_data.size() / 2; i > 0; i--) {
adjust(i,m_data.size() - 1);
}
}
void maxHeap::adjust(unsigned long index, unsigned long size) {
unsigned long child = 0;
for (; index <= size / 2; ) {
child = index * 2;
if (index + 1 <= size && m_data[child] < m_data[child + 1]) {
child++;
}
if (m_data[index] < m_data[child]) {
valueType tmp = m_data[index];
setValue(index, m_data[child]);
setValue(child, tmp);
index = child;
} else {
break;
}
}
return;
}
valueType maxHeap::getValue(unsigned long index) {
if (index > m_data.size() - 1) {
cout<<"Function getValue: Too bigger index"<<endl;
return m_data[0];
}
return m_data[index];
}
bool maxHeap:: setValue(unsigned long index,valueType value) {
if (index > m_data.size() - 1) {
cout<<"Function setValue: Too bigger index"<<endl;
return false;
}
m_data[index] = value;
return true;
}
void maxHeap::printMaxHeap() {
cout<<"printMaxHeap:"<<endl;
for (int i = 0; i < m_data.size(); i++) {
cout<<m_data[i]<<" ";
}
cout<<endl;
return;
}
valueType maxHeap::getMaxValue() {
return m_data[1];
}
最大堆的测试代码：
bool maxHeap_test() {
/* Init array. */
valueType a[] = {0,45,36,18,53,72,30,48,93,15,35};
int count = sizeof(a) / sizeof(valueType);
vector<valueType> data_test(a, a+count);
/* Init maxHeap. */
maxHeap* obj = new maxHeap(data_test, false);
/* Testing the methold of adjust. */
cout<<"maxHeap before adjust:"<<endl;
for (int i = 0; i < count; i++) {
cout<<a[i]<<" ";
}
cout<<endl;
cout<<"maxHeap after adjust:"<<endl;
obj->printMaxHeap();
/* Ending. */
/* Testing the methold of remove. */
cout<<"Testing the methold of remove."<<endl;
cout<<"Max value: "<<obj->getMaxValue()<<endl;
obj->remove(1);
cout<<"Max value: "<<obj->getMaxValue()<<endl;
obj->remove(1);
cout<<"Max value: "<<obj->getMaxValue()<<endl;
obj->remove(1);
cout<<"Max value: "<<obj->getMaxValue()<<endl;
cout<<"预期输出：93 72 53"<<endl;
/* Ending. */
if (NULL != obj) {
delete obj;
obj = NULL;
}
return true;
}
//
// main.cpp
// 100-alg-tests
//
// Created by bobkentt on 15-3-24.
// Copyright (c) 2015年 kedong. All rights reserved.
//
#include <iostream>
#include "2th.h"
#include "3th.h"
#include "4th.h"
#include "maxHeap.h"
int main(int argc, const char * argv[]) {
//test_1();
//test_2();
//test_3();
//test_4();
maxHeap_test();
return 0;
}
测试结果打印输出：
maxHeap before adjust:
0 45 36 18 53 72 30 48 93 15 35
maxHeap after adjust:
printMaxHeap:
0 93 72 48 53 45 30 18 36 15 35
Testing the methold of remove.
Max value: 93
Max value: 72
Max value: 53
Max value: 48
预期输出：93 72 53
Program ended with exit code: 0最大堆创建好之后的主要问题就是将此问题模型带入最大堆模型。那么代码如下：
头文件：
//
// 5th.h
// 100-alg-tests
//
// Created by bobkentt on 15-3-24.
// Copyright (c) 2015年 kedong. All rights reserved.
//
#ifndef ___00_alg_tests___th__
#define ___00_alg_tests___th__
#include <stdio.h>
void test_5_1();
#endif /* defined(___00_alg_tests___th__) */源文件：
//
// 5th.cpp
// 100-alg-tests
//
// Created by bobkentt on 15-3-24.
// Copyright (c) 2015年 kedong. All rights reserved.
//
#include <vector>
#include <iostream>
#include "5th.h"
#include "maxHeap.h"
using namespace std;
/*
5.查找最小的k 个元素
题目：输入n 个整数，输出其中最小的k 个。
例如输入1，2，3，4，5，6，7 和8 这8 个数字，则最小的4 个数字为1，2，3 和4。
*/
/*
*题目分析：
1.题目中要求输出最小的n各元素，但未要求输出的元素的顺序。
2.可以看出此题是一个传统的考察排序的题目。
3.那此题的目的就是考察选择那种排序算法使时间和空间复杂度最低了。
4.由于考虑时间复杂度和空间复杂度尽可能的小。那么想想看看有没有线性
的算法解决这个问题。首先想到的是取任意k个数构建一个最大堆，然后
选取后面的n-k个数与最大堆进行比较，若比最大值的元素值小，那
么对最大堆进行调整。OK想一下这种方法的时间复杂度。用调整法构建一
个k个元素的最大堆需要O(k)的时间复杂度，假设后序n-k个元素在最坏情
况都比最大堆的最大元素小，那么时间复杂度是：O(n-k + (n-k)logn)
经过计算这种方法总的时间复杂度是O(nlogk)。
这样与我的原目标不想符不过这也不失是一个好办法。代码参见解法1.
*/
/// @param <obj> <IN OUT> <INPUT array>
/// @param <obj> <IN> <OUTPUT value number>
void func_5th_m1(vector<valueType> &obj,int k) {
/* Init the heap which have k elements. */
vector<valueType> tmp;
vector<valueType> ::iterator iter = obj.begin();
iter+=k;
tmp.insert(tmp.begin(), obj.begin(), iter);
cout<<"The vector tmp:";
for (int i = 0; i < tmp.size(); i++) {
cout<<tmp[i]<<" ";
}
cout<<endl;
maxHeap* heap = new maxHeap(tmp, false);
/* 选取后面的n-k个数与最大堆进行比较，若比最大值的元素值小，
那么对最大堆进行调整 */
for (int i = k-1; i < obj.size(); i++) {
valueType maxValueOfHeap = heap->getMaxValue();
if (maxValueOfHeap > obj[i]) {
/* Remove the maxium value of the heap. */
heap->remove(1);
heap->insert(obj[i]);
}
}
heap->printMaxHeap();
return;
}
void test_5_1() {
#define TEST_K 5
/* Init array. */
valueType a[] = {0,45,36,18,53,72,30,48,93,15,35};
int count = sizeof(a) / sizeof(valueType);
vector<valueType> data_test(a, a+count);
func_5th_m1(data_test,TEST_K);
return;
}打印输出结果：
The vector tmp:0 45 36 18 53
printMaxHeap:
0 35 30 18 15
Program ended with exit code: 0
用最大堆得方法可以实现log(nlogk)的时间复杂度，继续寻找线性的时间复杂度。这个题目给人一种快速排序的感觉，自然想到了随机选择的算法。主体思想就是：在序列中随机的选择主元，然后进行类似于快速排序的划分。《算法导论》对这种方法进行过讨论，网络上给的时间复杂度是O(n)。
于是搞一下，查看了一下算法导论，随机选择
RANDOMIZED-SELECT(A, p, r)
伪代码如下：
PARTITION(A, p, r) //partition过程 p为第一个数，r为最后一个数
1 x ← A[r] //以最后一个元素作为主元
2 i ← p - 1
3 for j ← p to r - 1
4 do if A[j] ≤ x
5 then i ← i + 1
6 exchange A[i] <-> A[j]
7 exchange A[i + 1] <-> A[r]
8 return i + 1
RANDOMIZED-PARTITION(A, p, r) //随机快排的partition过程
1 i ← RANDOM(p, r) //i 随机取p到r中个一个值
2 exchange A[r] <-> A[i] //以随机的 i作为主元
3 return PARTITION(A, p, r) //调用上述原来的partition过程
RANDOMIZED-SELECT(A, p, r, i) //以线性时间做选择，目的是返回数组A[p..r]中的第i 小的元素
1 if p = r //p=r，序列中只有一个元素
2 then return A[p]
3 q ← RANDOMIZED-PARTITION(A, p, r) //随机选取的元素q作为主元
4 k ← q - p + 1 //k表示子数组 A[p…q]内的元素个数，处于划分低区的元素个数加上一个主元元素
5 if i == k //检查要查找的i 等于子数组中A[p....q]中的元素个数k
6 then return A[q] //则直接返回A[q]
7 else if i < k
8 then return RANDOMIZED-SELECT(A, p, q - 1, i)
//得到的k 大于要查找的i 的大小，则递归到低区间A[p，q-1]中去查找
9 else return RANDOMIZED-SELECT(A, q + 1, r, i - k)
//得到的k 小于要查找的i 的大小，则递归到高区间A[q+1，r]中去查找。 这个问题的思路参考了网上大神July的思想，大神的这篇博客的地址：
http://blog.csdn.net/v_JULY_v/article/details/6370650
版权声明：本文为bobkentblog原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。