//本次练习的是 堆排序 和 堆的大数据应用//堆排序的时间复杂度为 O(n)//堆的大数据应用应选择 小堆 进行处理//但 当数据超过100000时速度明显变慢,可能是建立小堆的时候慢 》》》》》有没有更优的方法#include<iostream>#include<vector>#include<time.h>using namespace std;//........................以下为 堆排序.....................................void AdjustDownGreater(vector<int>& 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<int>& h,size_t size){ while (size > 1) { swap(h[0], h[size - 1]); size--; AdjustDownGreater(h,size); }}void Print(vector<int>& 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<int> 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<int>& h){ srand(time(0)); for (int i = 0; i < N; i++) { h.push_back(rand() % N + 1); }}void AdjustDownLess(vector<int>& 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<int>& h, vector<int>& 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<int>& h){ for (int i = 0; i < K; i++) { cout << h[i]<<" "; }}void Test2(){ vector<int> h; vector<int> greatest; GetData(h); GetGreatestK(h, greatest); Print(greatest);}int main(){ //Test1(); Test2(); return 0;}
本文转自 ye小灰灰 51CTO博客,原文链接:http://blog.51cto.com/10704527/1762368,如需转载请自行联系原作者