详解python之heapq模块及排序操作

Python  /  管理员 发布于 7年前   374

说到排序，很多人可能第一想到的就是sorted,但是你可能不知道python中其实还有还就中方法哟，并且好多种场景下效率都会比sorted高。那么接下来我就依次来介绍我所知道的排序操作。

sorted(iterable, *, key=None, reverse=False)

list1=[1,6,4,3,9,5]list2=['12','a6','4','c34','b9','5']print(sorted(list1)) #[1, 3, 4, 5, 6, 9]print(sorted(list2)) #['12', '4', '5', 'a6', 'b9', 'c34']#总结上面两种排序：字符串排序根据元素首字符的ASCII比较进行排序，#数字类型按照大小排序，数字不能混合排序list3=[ {'name':'jim','age':23,'price':500}, {'name':'mase','age':23,'price':600}, {'name':'tom','age':25,'price':2000}, {'name':'alice','age':22,'price':300}, {'name':'rose','age':21,'price':2400},]print(sorted(list3,key=lambda s:(s['age'],s['price'])))#[{'name': 'rose', 'age': 21, 'price': 2400}, {'name': 'alice', 'age': 22, 'price': 300}, {'name': 'jim', 'age': 23, 'price': 500}, {'name': 'mase', 'age': 23, 'price': 600}, {'name': 'tom', 'age': 25, 'price': 2000}]最后的reverse参数我就不作说明了，就是把结果进行倒序，可用作降序排列介绍一种比lambda效率高的方式：operator模块中的方法itemgetter>>> itemgetter(1)('ABCDEFG')'B'>>> itemgetter(1,3,5)('ABCDEFG')('B', 'D', 'F')>>> itemgetter(slice(2,None))('ABCDEFG')'CDEFG运用到上述代码print(sorted(list3,key=itemgetter('age','price'))) #结果同上但效率会比较高

接下来的排序操作涉及到一个非常重要的一种数据结构――堆，不过今天我主要介绍这个模块中的方法，具体什么是堆，及其还有一种数据结构――栈，有时间我会专门写一篇文章来介绍。

heapq(Python内置的模块)

__all__ = ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge',
           'nlargest', 'nsmallest', 'heappushpop']

接下来我们一一介绍。

nlargest与nsmallest,通过字面意思可以看出方法大致的作用，接下来动手测验

nlargest(n, iterable, key=None)nsmallest(n, iterable, key=None)#n:查找个数 iterable:可迭代对象 key：同sortedlist1=[1,6,4,3,9,5]list2=['12','a6','4','c34','b9','5']list3=[ {'name':'jim','age':23,'price':500}, {'name':'mase','age':23,'price':600}, {'name':'tom','age':25,'price':2000}, {'name':'alice','age':22,'price':300}, {'name':'rose','age':21,'price':2400},]from operator import itemgetterimport heapqprint(heapq.nlargest(len(list1),list1))print(heapq.nlargest(len(list2),list2))print(heapq.nlargest(len(list3),list3,key=itemgetter('age','price')))#以上代码输出结果同sortedprint(heapq.nsmallest(len(list1),list1))print(heapq.nsmallest(len(list2),list2))print(heapq.nsmallest(len(list3),list3,key=itemgetter('age','price')))#结果是降序[1, 3, 4, 5, 6, 9]['12', '4', '5', 'a6', 'b9', 'c34'][{'name': 'rose', 'age': 21, 'price': 2400}, {'name': 'alice', 'age': 22, 'price': 300}, {'name': 'jim', 'age': 23, 'price': 500}, {'name': 'mase', 'age': 23, 'price': 600}, {'name': 'tom', 'age': 25, 'price': 2000}]

heappush,heappop,heapify,heapreplace,heappushpop

堆结构特点：heap[0]永远是最小的元素(利用此特性排序)

heapify：对序列进行堆排序，
heappush:在堆序列中添加值
heappop:删除最小值并返回
heappushpop:添加并删除堆中最小值且返回，添加之后删除
heapreplace:添加并删除队中最小值且返回，删除之后添加

nums=[54,23,64.,323,53,3,212,453,65]heapify(nums)  #先进行堆排序print(heappop(nums))  #3print(heappush(nums,50))  #添加操作，返回Noneprint(heappushpop(nums,10))  #由于是添加后删除，所以返回10print(heappop(nums))  #23print(heapreplace(nums,10))  #和heappushpop，返回50print(nums)  #[10, 53, 54, 65, 323, 64.0, 212, 453]

merge：合并多个序列

list1 = [1, 2, 3, 4, 5, 12]set1 = {2, 3, 9, 23, 54}s = list(merge(list1,set1))print(s)  #[1, 2, 2, 3, 3, 4, 5, 9, 12, 54, 23]#发现输出结果不仅进行了合并，还进行了排序，有意思哈，可是换个代码测验，你再看一下list1 = [31, 2, 83, 24, 5, 12]set1 = {2, 83, 9, 23, 54}s = list(merge(list1,set1))print(s)  #[2, 9, 31, 2, 83, 24, 5, 12, 83, 54, 23]#你们肯定想这是什么鬼，一点都没有头绪，其实经过我的多次测验，还是有规律的，但是由于没有什么作用就不大篇幅说明了，喜欢刨根问题的小伙伴可以尝试自己思考一下。

小伙伴们有没有想我为何介绍这个模块，并且和排序放在一起呢，其实在很多时候我们需要找序列中的前几个最大值或者最小值，使用此模块中的方法是最好不过的了。

如果需要全部排序我们使用sorted，需要查找最大或最小的几个或者多个我们使用alargest/asmallest,查找最大最小使用max/min