海量数据中找出最大的前100个（find_topk）最小堆算法-洪萨配资

我来帮你实现这个寻找前100个最大数据的算法。这个算法的时间复杂度是O(n log 100)，空间复杂度是O(100)。

C++实现

#include<iostream>#include<vector>#include<queue>#include<functional>#include<random>usingnamespacestd;// 寻找前k个最大元素的算法vector<int>findTopK(constvector<int>&nums,intk){if(nums.size()<=k){vector<int>result(nums.begin(),nums.end());returnresult;}// 创建最小堆priority_queue<int,vector<int>,greater<int>>minHeap;// 步骤1: 插入前k个元素for(inti=0;i<k;i++){minHeap.push(nums[i]);}// 步骤2-3: 遍历剩余元素，维护堆for(size_t i=k;i<nums.size();i++){if(nums[i]>minHeap.top()){minHeap.pop();// 弹出堆顶minHeap.push(nums[i]);// 插入当前元素}}// 步骤4: 堆中元素即为前k个最大数据vector<int>result;while(!minHeap.empty()){result.push_back(minHeap.top());minHeap.pop();}returnresult;}intmain(){// 生成测试数据vector<int>data(1000);random_device rd;mt19937gen(rd());uniform_int_distribution<>dis(1,10000);for(inti=0;i<1000;i++){data[i]=dis(gen);}intk=100;vector<int>topK=findTopK(data,k);cout<<"前"<<k<<"个最大元素："<<endl;for(size_t i=0;i<topK.size();i++){cout<<topK[i]<<" ";if((i+1)%10==0)cout<<endl;}cout<<endl;return0;}

Python实现

importheapqimportrandomfromtypingimportListdeffind_top_k(nums:List[int],k:int)->List[int]:""" 寻找前k个最大元素的算法 实现步骤： 1. 创建一个最小堆并将前k个数据插入堆中 2. 遍历剩余的数据，如果当前数据比堆顶大，就替换堆顶元素 3. 继续遍历所有数据，确保堆中保留的是最大的k个数据 4. 遍历完成后，堆中的元素就是前k个最大的数据 """iflen(nums)<=k:returnsorted(nums,reverse=True)# 步骤1: 创建最小堆并插入前k个元素min_heap=nums[:k]heapq.heapify(min_heap)# 建立最小堆# 步骤2-3: 遍历剩余元素，维护堆fornuminnums[k:]:ifnum>min_heap[0]:# 如果当前元素比堆顶大# 弹出堆顶，插入当前元素heapq.heapreplace(min_heap,num)# 步骤4: 堆中元素即为前k个最大数据# 堆是最小堆，需要排序后返回result=sorted(min_heap,reverse=True)returnresultdeffind_top_k_alternative(nums:List[int],k:int)->List[int]:"""另一种实现方式，更清晰地体现算法步骤"""iflen(nums)<=k:returnsorted(nums,reverse=True)# 步骤1: 创建最小堆并插入前k个元素min_heap=[]foriinrange(k):heapq.heappush(min_heap,nums[i])# 步骤2-3: 遍历剩余数据foriinrange(k,len(nums)):ifnums[i]>min_heap[0]:# 比堆顶大# 我就往堆里面插heapq.heappop(min_heap)# 弹出堆顶heapq.heappush(min_heap,nums[i])# 插入当前数据# 步骤4: 返回结果returnsorted(min_heap,reverse=True)defmain():# 生成测试数据random.seed(42)data=[random.randint(1,10000)for_inrange(1000)]k=100# 使用方法1top_k=find_top_k(data,k)print(f"前{k}个最大元素：")fori,numinenumerate(top_k,1):print(f"{num:6d}",end=" ")ifi%10==0:print()print()# 验证结果正确性sorted_data=sorted(data,reverse=True)[:k]print(f"算法结果是否正确:{top_k==sorted_data}")# 使用方法2top_k2=find_top_k_alternative(data,k)print(f"方法2结果是否正确:{sorted(top_k2)==sorted(top_k)}")if__name__=="__main__":main()