//本次练习的是  堆排序  和 堆的大数据应用
//堆排序的时间复杂度为  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;
}

成都创新互联公司坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站设计、成都做网站、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的舟山网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

名称栏目：堆排序和堆的大数据应用-创新互联
URL网址：http://ybzwz.com/article/cshghs.html