//本次练习的是   堆排序   和  堆的大数据应用
//堆排序的时间复杂度为   O（n）
//堆的大数据应用应选择   小堆   进行处理
//但  当数据超过100000时速度明显变慢，可能是建立小堆的时候慢   》》》》》有没有更优的方法



#include
#include
#include
using namespace std;


//........................以下为  堆排序.....................................
void AdjustDownGreater(vector& h,size_t size)//建立大堆
{
    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& h,size_t size)
{
    while (size > 1)
    {
        swap(h[0], h[size - 1]);
        size--;

        AdjustDownGreater(h,size);
    }

}

void Print(vector& h,size_t size)
{
    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 h;
    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& h)
{
    srand(time(0));
    for (int i = 0; i < N; i++)
    {
        h.push_back(rand() % N + 1);
    }
}

void AdjustDownLess(vector& h, size_t size)//建立小堆
{
    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& h, vector& greatest)
{
    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& h)
{
    for (int i = 0; i < K; i++)
    {
        cout << h[i]<<"  ";
    }
}

void Test2()
{
    vector h;
    vector greatest;
    GetData(h);
    GetGreatestK(h, greatest);
    Print(greatest);
}


int main()
{
    //Test1();
    Test2();

    return 0;
}

成都一家集口碑和实力的网站建设服务商，拥有专业的企业建站团队和靠谱的建站技术，10年企业及个人网站建设经验 ,为成都上1000家客户提供网页设计制作,网站开发,企业网站制作建设等服务,包括成都营销型网站建设，品牌网站设计，同时也为不同行业的客户提供成都网站设计、网站建设的服务,包括成都电商型网站制作建设,装修行业网站制作建设，传统机械行业网站建设,传统农业行业网站制作建设。在成都做网站,选网站制作建设服务商就选创新互联。

文章题目：堆排序 和堆的大数据应用
文章分享：http://chengdu.cdxwcx.cn/article/jcdsds.html