成都网站建设设计

将想法与焦点和您一起共享

堆的简单应用-创新互联

一、大数据的处理

站在用户的角度思考问题,与客户深入沟通,找到延川网站设计与延川网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都网站设计、成都做网站、企业官网、英文网站、手机端网站、网站推广、国际域名空间、网络空间、企业邮箱。业务覆盖延川地区。

给出N个数据,要求找到并输出这N个数里面大的K个数

思路:利用堆,先建一个开辟一个大小为K的数组,从N个数据里拿出K个数据放到堆里面,然后再通过向

下调整法把堆调整为最小堆,此时数组的第一个元素就是堆里面最小的元素,然后在剩下的N-K个

数据中依次和堆里面最小的数据进行比较,若比第一个元素大,则交换两个的值,每交换一次就向下调

整一次,保证在最上面的是最小元素,这样一直到所有数据比较完毕,此时堆里面存储的k个数据就是最

大的k个数据。

下面是实现代码

#include
#include

using namespace std;
//1.在N个数据当中找出大的K个数

const int N = 10000;
const int K = 100;

void AdjustDown1(int a[], int size, int parent)  //建一个小堆
{
int child = parent * 2 + 1;

while (child < K)
{
if ((child + 1 < K) && (a[child + 1] < a[child]))
{
child++;
}

if (a[child] < a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}

}

void GetTopK(int a[],int TopK[])
{
assert(K < N);
int i = 0;
int j = 0;
int m = 0;
int n = 0;

for (i = 0; i < K; i++)
{
TopK[i] = a[i];     //取出a中的前k个数字放到topk[]里面
}

//建堆

for (j = (K - 2) / 2; j >0; --j)
{
AdjustDown1(TopK,K,j);
}

for (int m = 0; m < N; ++m)
{
if (a[m]>TopK[0])
{
TopK[0] = a[m];
AdjustDown1(TopK, K, 0);
}
}

for (int n = 0; n < K; ++n)  //一次输出K个大数
{
cout << TopK[n] << " ";
}
cout << endl;
}

测试代码

#include"BIgData.h"

void TestTopK()
{
int a[N];
int TopK[K];

for (int i = 0; i < N; ++i)
{
a[i] = i;
}

GetTopK(a, TopK);

}
int main()
{
TestTopK();
system("pause");
return 0;
}

测试结果

堆的简单应用

为了便于调试,我用的测试栗子比较简单,大家可以尝试一下更一般的栗子哦~

二.堆排序

思路:利用堆,建一个大堆,每次选出大的数据与数组末尾的数据进行交换,然后再进行一次向下

调整变成大堆,始终保持最上面的为当前大的数据,假设数组由n个数据,则下次就让第一个数据与

数组的第n-1个数据作比较,因为第n个数据已经是大的了,每交换一次要调整一次,这样当比较到第

一个数据时这个堆就是一个有序的了。

实现代码如下:

//2.堆排序:建大堆,每次找到大的数据交换到数组末尾,将剩下的数据AdjustDown,再进行交换
void AdjustDown2(int a[],int size,size_t parent)
{
int child = parent * 2 + 1;

while (child{
if ((child + 1 < size)&&a[child] < a[child + 1])
{
++child;
}

if (a[child] > a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}

void Heap_Sort(int a[], size_t n)
{
for (int i = (n - 2) / 2; i >= 0; i--)  //注意边界条件
{
AdjustDown2(a, n, i);
}

for (int i = 0; i < n; ++i)
{
swap(a[0], a[n - 1-i]);

AdjustDown2(a, n - 1 - i, 0);
}

for (int i = 0; i < n; ++i)
{
cout << a[i] << " ";
}
cout << endl;

}

测试代码:

void TestHeap_Sort()
{
int a[] = { 10, 12, 9, 15, 13, 17, 16, 18, 20,14 };
Heap_Sort(a, 10);
}

int main()
{
TestHeap_Sort();
system("pause");
return 0;
}

测试结果:

堆的简单应用

以上便是堆的两种简单应用啦,不足之处还请大家指出哦~

创新互联www.cdcxhl.cn,专业提供香港、美国云服务器,动态BGP最优骨干路由自动选择,持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证, 机房独有T级流量清洗系统配攻击溯源,准确进行流量调度,确保服务器高可用性。佳节活动现已开启,新人活动云服务器买多久送多久。


新闻标题:堆的简单应用-创新互联
分享网址:http://chengdu.cdxwcx.cn/article/gjooc.html