自定义类使用heapq堆操作"/>
随笔——Python中对自定义类使用heapq堆操作
随笔——Python中对自定义类使用heapq堆操作
前言
由于最近在完成八数码的A*搜索大作业,那么很显然对于八数码的每一个状态应该是用一个矩阵来表示,并且可以将这些状态按其 f ( n ) f(n) f(n)值放到最小堆里,这样的话每次从最小堆里取出一个元素,就可以达到A*搜索的目的。用C++语言倒是很好完成,但这次想用Python来完成,所以花了不少功夫来研究Python怎么实现自定义类的最小堆
实现
查阅资料发现Python自带heapq库,那么我们唯一需要做的就是对自定义类判断大小的方式进行重写了。查了老半天资料才发现是重写自定义类的__lt__函数,这样就可以实现自定义排序的需求了
示例代码
import heapq
import numpy as np
class test:def __init__(self):self.A=np.zeros((3,4),dtype=int)def __lt__(self,other):if self.A[0][0]<other.A[0][0]:return Trueelse:return False
c=[]
a=test()
b=test()
a.A[0][0]=5
b.A[0][0]=1
heapq.heappush(c, a)
heapq.heappush(c, b)
#d=heapq.heappop(c)
heapq.heappop(c)
print(heapq.nlargest(2, c)[0].A[0][0])
#print(d.A[0][0])
这里根据test类对象的A[0][0]来作为比较的对象(可以任意定义),测试后发现满足要求
注意:这里的__lt__中的l是小写的L而不是大写的i
其他
想到这里突然想到C++STL中排序中一个比较有意思的现象
对于priority_queue使用仿函数greater代表的是最小堆,less代表的是最大堆
而sort排序中使用greater是指降序排列,less是指升序排列
其实这跟操作数的顺序有关,对于priority_queue我们在排序的时候,是拿要插入的数和现在堆内的数对比,也就是说如果使用greater的话,如果插入的数比当前数大,那么他就会插在当前数前面,也就形成了前面的数会比后面的数小,也就是最小堆
而sort中我们在排序的时候,序列中的数是已经确定的,相当于是拿前面的数和后面的数比,如果前面的数大于后面的数就会插在前面,否则就会移动到后面,这样以来就是降序排列了
其实这也算是一个困扰自己许久的问题,今天终于得到了解决
更多推荐
随笔——Python中对自定义类使用heapq堆操作
发布评论