Python中自带的堆heapq,不支持自定义的比较函数。 这导致，heapq中的元素，如果是结构体的话，不太方便。
实现了一个支持自定义比较函数的Heap类。
|
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
28
29
30
31
32
33
34
35
36 |
import
heapqimport
randomclass
MyHeap(object): def
__init__(self, initial=None, key=lambda
x:x): self.k =
20 # the Size of this Heap self.key =
key self._data =
[] def
push(self, item): if
len(self._data) < self.k: heapq.heappush(self._data, (self.key(item), item)) else: topk_small =
list(self._data[0]) if
item.a > topk_small[1].a: heapq.heapreplace(self._data, (self.key(item), item)) def
pop(self): if(len(self._data)>1): return
heapq.heappop(self._data)[1] else: return
Noneclass
Element(): def
__init__(self, a,b,c): self.a =
a self.b =
b self.c =
cmyHeap =
MyHeap(key=lambda
item:item.a)for
i in
range(100): a =
random.randint(0,100); b =
random.randint(0,100); myHeap.push(Element(a,b,b))for
i in
range(20): j =
myHeap.pop() if(j!=None): print
""+str(j.a) + "\t" +
str(j.b) |
python中的堆支持自定义的比较函数 - Heap in Python with comparator.,布布扣,bubuko.com
python中的堆支持自定义的比较函数 - Heap in Python with comparator.
原文：http://www.cnblogs.com/yaozhaoyz/p/3595842.html