http://www.coder4.com/archives/3844
需1求：给出N长的序列，求出TopK大的元素，使用小顶堆，heapq模块实现。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
import heapq
import random
class TopkHeap(object):
def __init__(self, k):
self.k = k
self.data = []
def Push(self, elem):
if len(self.data) < self.k:
heapq.heappush(self.data, elem)
else:
topk_small = self.data[0]
if elem > topk_small:
heapq.heapreplace(self.data, elem)
def TopK(self):
return [x for x in reversed([heapq.heappop(self.data) for x in xrange(len(self.data))])]
if __name__ == "__main__":
print "Hello"
list_rand = random.sample(xrange(1000000), 100)
th = TopkHeap(3)
for i in list_rand:
th.Push(i)
print th.TopK()
print sorted(list_rand, reverse=True)[0:3]
|
上面的用heapq就能轻松搞定。
变态的需求来了：给出N长的序列，求出BtmK小的元素，即使用大顶堆。
heapq在实现的时候，没有给出一个类似Java的Compartor函数接口或比较函数，开发者给出了原因见这里：http://code.activestate.com/lists/python-list/162387/
于是，人们想出了一些很NB的思路，见：http://stackoverflow.com/questions/14189540/python-topn-max-heap-use-heapq-or-self-implement
我来概括一种最简单的：
将push(e)改为push(-e)、pop(e)改为-pop(e)。
也就是说，在存入堆、从堆中取出的时候，都用相反数，而其他逻辑与TopK完全相同，看代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class BtmkHeap(object):
def __init__(self, k):
self.k = k
self.data = []
def Push(self, elem):
# Reverse elem to convert to max-heap
elem = -elem
# Using heap algorighem
if len(self.data) < self.k:
heapq.heappush(self.data, elem)
else:
topk_small = self.data[0]
if elem > topk_small:
heapq.heapreplace(self.data, elem)
def BtmK(self):
return sorted([-x for x in self.data])
|
经过测试，是完全没有问题的，这思路太Trick了……
