topk算法实现

**Top-K算法实现**

Top-K算法是一种常见的排序算法，用于从一个集合中找出前K个最大的元素或最小的元素。这种算法在机器学习、信息检索等领域有广泛应用。

###1. Top-K算法原理Top-K算法的基本思想是：首先对整个集合进行排序，然后取前K个元素作为结果。这一过程可以通过堆数据结构来实现，堆是一种特殊的二叉树，每个节点都满足以下性质：

* 每个父节点的值都大于或等于其左右子节点的值（对于最大堆）或小于或等于其左右子节点的值（对于最小堆）。

###2. Top-K算法实现下面是Top-K算法的Python实现代码：

import heapqclass MaxHeap:
 def __init__(self):
 self.heap = []

 def push(self, value):
 """将一个元素推入堆中"""
 heapq.heappush(self.heap, -value)

 def pop(self):
 """弹出堆顶元素"""
 return -heapq.heappop(self.heap)

class MinHeap:
 def __init__(self):
 self.heap = []

 def push(self, value):
 """将一个元素推入堆中"""
 heapq.heappush(self.heap, value)

 def pop(self):
 """弹出堆顶元素"""
 return heapq.heappop(self.heap)


class TopK:
 def __init__(self, k):
 self.k = k self.max_heap = MaxHeap()
 self.min_heap = MinHeap()

 def add(self, num):
 """添加一个数字到堆中"""
 if len(self.max_heap.heap) < self.k:
 self.max_heap.push(num)
 else:
 if num > self.max_heap.pop():
 self.max_heap.push(num)

 if len(self.min_heap.heap) < self.k:
 self.min_heap.push(num)
 else:
 if num < self.min_heap.pop():
 self.min_heap.push(num)

 def get_top_k(self):
 """获取前K个最大或最小的元素"""
 return sorted([self.max_heap.pop() for _ in range(len(self.max_heap.heap))], reverse=True)


# 测试topk = TopK(3)
topk.add(5)
topk.add(2)
topk.add(8)
topk.add(1)
topk.add(9)

print(topk.get_top_k()) # [9,8,5]