//本次练习的是 堆排序 和 堆的大数据应用
//堆排序的时间复杂度为 O(n)
//堆的大数据应用应选择 小堆 进行处理
//但 当数据超过100000时速度明显变慢,可能是建立小堆的时候慢 》》》》》有没有更优的方法
#include
#include
#include
using namespace std;
//........................以下为 堆排序.....................................
void AdjustDownGreater(vector
{
if (size <= 1) //注意参数检测啊....
{
return;
}
for (int parent = (size - 1 - 1) / 2; parent >= 0; parent--) //经验:可以先写内层循环,再写外层循环
{
while(parent <= size - 1)
{
int leftcChild = 2 * parent + 1;
if (leftcChild + 1 <= size - 1 && h[leftcChild] < h[leftcChild + 1])
{
leftcChild++;
}
if (leftcChild <= size - 1 && h[parent] < h[leftcChild])
{
swap(h[parent], h[leftcChild]);
parent = leftcChild;
}
else
{
break;
}
}
}
}
void HeapSort(vector
{
while (size > 1)
{
swap(h[0], h[size - 1]);
size--;
AdjustDownGreater(h,size);
}
}
void Print(vector
{
for (int i = 0; i < size; i++)
{
cout << h[i]<<" ";
}
}
void Test1()
{
int arr[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };
vector
for (int i = 0; i < 10; i++)
{
h.push_back(arr[i]);
}
AdjustDownGreater(h, 10);
HeapSort(h, 10);
Print(h, 10);
}
//..................................以下为堆大数据应用....................
//从n个数据中选出前k个最大的数 用的是 *******《小堆》**********************
//选择小堆的原因:用一个数组来存储k个数arr[k] 如果选出的第一个数就是最大的那个,那后面的就进不了arr了
const int N = 100000; //当超过100000时速度明显变慢 《《《《有没有更优的方法》》》
const int K = 10;
void GetData(vector
{
srand(time(0));
for (int i = 0; i < N; i++)
{
h.push_back(rand() % N + 1);
}
}
void AdjustDownLess(vector
{
if (size <= 1)
{
return;
}
for (int parent = (size - 1 - 1) / 2; parent >= 0; parent--)
{
while (parent <= size - 1)
{
int leftcChild = 2 * parent + 1;
if (leftcChild + 1 <= size - 1 && h[leftcChild] > h[leftcChild + 1])
{
leftcChild++;
}
if (leftcChild <= size - 1 && h[parent] > h[leftcChild])
{
swap(h[parent], h[leftcChild]);
parent = leftcChild;
}
else
{
break;
}
}
}
}
void GetGreatestK(vector
{
AdjustDownLess(h, N);
for (int i = 0; i < K; i++) //把前K个较小的push进去
{
greatest.push_back(h[i]);
}
for (int index = K; index < N; index++)
{
AdjustDownLess(greatest, K); //为了得到最小的数
if (h[index] > greatest[0]) //换掉最小的数
{
greatest[0] = h[index];
}
}
}
void Print(vector
{
for (int i = 0; i < K; i++)
{
cout << h[i]<<" ";
}
}
void Test2()
{
vector
vector
GetData(h);
GetGreatestK(h, greatest);
Print(greatest);
}
int main()
{
//Test1();
Test2();
return 0;
}
成都一家集口碑和实力的网站建设服务商,拥有专业的企业建站团队和靠谱的建站技术,10年企业及个人网站建设经验 ,为成都上1000家客户提供网页设计制作,网站开发,企业网站制作建设等服务,包括成都营销型网站建设,品牌网站设计,同时也为不同行业的客户提供成都网站设计、网站建设的服务,包括成都电商型网站制作建设,装修行业网站制作建设,传统机械行业网站建设,传统农业行业网站制作建设。在成都做网站,选网站制作建设服务商就选创新互联。