python中怎么实现队列的创建(python 堆和优先队列的使用详解)
python中怎么实现队列的创建
python 堆和优先队列的使用详解1.heapq
python里面的堆是通过在列表中维护堆的性质实现的。这一点与C++中heap一系列的算法类似,底层是通过堆vector的维护获取堆的性质。
关于二叉树
二叉树的特点:
二叉树是一种存储数据元素的汇集数据结构。
二叉树最重要的性质就是树的高度和树中可以容纳的最大结点个数之间的关系。树的高度类似于表长,是从根结点到其他结点的最大距离。在长为n的表里只能容纳n个结点,而在高为h的二叉树中则可以容纳大约2^h个结点,这是表和树的最大不同点。
一般的元素插入,如果是按线性顺序排列的,那么操作必然需要O(n)的时间(需要对n个数据进行移位处理),要突破这个限制,必须考虑其他数据结构的组织方式。二叉树就是一种高效插入的存储方式。
堆排序利用的是完全二叉树。
python堆的部分API,其他API查阅文档python_heap_API和 heapq的源代码
|
import heapq #向堆中插入元素,heapq会维护列表heap中的元素保持堆的性质 heapq.heappush(heap, item) #heapq把列表x转换成堆 heapq.heapify(x) #从可迭代的迭代器中返回最大的n个数,可以指定比较的key heapq.nlargest(n, iterable[, key]) #从可迭代的迭代器中返回最小的n个数,可以指定比较的key heapq.nsmallest(n, iterable[, key]) #从堆中删除元素,返回值是堆中最小或者最大的元素 heapq.heappop(heap) |
1.1.内置类型
从上述源代码可以看出来,heapq使用的内置的小于号,或者类的__lt__比较运算来进行比较。
|
def heapq_int(): heap = [] #以堆的形式插入堆 heapq.heappush(heap, 10 ) heapq.heappush(heap, 1 ) heapq.heappush(heap, 10 / 2 ) [heapq.heappush(heap,i) for i in range ( 10 )] [heapq.heappush(heap, 10 - i) for i in range ( 10 )] #最大的10个元素 print heapq.nlargest( 10 ,heap) #输出所有元素 print [heapq.heappop(heap) for i in range ( len (heap))] |
1.2.元组类型
元素会默认调用内置比较函数cmp
|
def heapq_tuple(): heap = [] #向推中插入元组 heapq.heappush(heap,( 10 , 'ten' )) heapq.heappush(heap,( 1 , 'one' )) heapq.heappush(heap,( 10 / 2 , 'five' )) while heap: print heapq.heappop(heap), print |
1.2.类类型
类类型,使用的是小于号_lt_,当然没有重写但是有其他的比较函数例如:_le_,_gt_,_cmp_,也是会调用的,和小于号等价的都可以调用(测试了gt),具体的这些操作之间的关系我也没有研究过。如果类里面没有重写_lt_,会调用其他的比较操作符,从源代码可以看出来,如果没有_lt_,那么会调用_ge_函数。
所以可以重写上述的那些函数:
|
class Skill( object ): def __init__( self ,priority,description): self .priority = priority self .description = description def __lt__( self ,other): #operator < return self .priority < other.priority def __ge__( self ,other): #oprator >= return self .priority > = other.priority def __le__( self ,other): #oprator <= return self .priority < = other.priority def __cmp__( self ,other): #call global(builtin) function cmp for int return cmp ( self .priority,other.priority) def __str__( self ): return '(' + str ( self .priority) + ',\'' + self .description + '\')' def heapq_class(): heap = [] heapq.heappush(heap,Skill( 5 , 'proficient' )) heapq.heappush(heap,Skill( 10 , 'expert' )) heapq.heappush(heap,Skill( 1 , 'novice' )) while heap: print heapq.heappop(heap), print |
所以如果要用到自己定义的类型,可以重写上述函数,就可以使用heapq函数了。
2.PriorityQueue
PriorityQueue的python源代码PriorityQueue
从源代码可以看出来,PriorityQueue使用的就是heapq来实现的,所以可以认为两者算法本质上是一样的。当然PriorityQueue考虑到了线程安全的问题。
下面给出PriorityQueue的部分API和使用方法。
参考Queue
|
#向队列中添加元素 Queue.put(item[, block[, timeout]]) #从队列中获取元素 Queue.get([block[, timeout]]) #队列判空 Queue.empty() #队列大小 Queue.qsize() |
2.1.内置类型
直接调用内置函数cmp进行比较
|
try : import Queue as Q #python version < 3.0 except ImportError: import queue as Q #python3.* def PriorityQueue_int(): que = Q.PriorityQueue() que.put( 10 ) que.put( 1 ) que.put( 5 ) while not que.empty(): print que.get(), print |
2.2.元组类型
|
def PriorityQueue_tuple(): que = Q.PriorityQueue() que.put(( 10 , 'ten' )) que.put(( 1 , 'one' )) que.put(( 10 / 2 , 'five' )) while not que.empty(): print que.get(), print |
2.2.自定义类型
|
class Skill( object ): def __init__( self ,priority,description): self .priority = priority self .description = description #下面两个方法重写一个就可以了 def __lt__( self ,other): #operator < return self .priority < other.priority def __cmp__( self ,other): #call global(builtin) function cmp for int return cmp ( self .priority,other.priority) def __str__( self ): return '(' + str ( self .priority) + ',\'' + self .description + '\')' def PriorityQueue_class(): que = Q.PriorityQueue() skill5 = Skill( 5 , 'proficient' ) skill6 = Skill( 6 , 'proficient6' ) que.put(skill6) que.put(Skill( 5 , 'proficient' )) que.put(Skill( 10 , 'expert' )) que.put(Skill( 1 , 'novice' )) while not que.empty(): print que.get(), print |
其他的一些方法的使用还是需要参考给出的文档的。
最后一点,让我比较奇怪的是(可能我并没有找到),没有提供像排序函数那样,指定比较方法函数,这点和c++有点区别。
这篇文档参考:参考文档
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持开心学习网。
原文链接:https://blog.csdn.net/liu2012huan/article/details/53264162
- python 数据库实现学生管理系统(python+mysql实现教务管理系统)
- python调用excel教程(利用python在excel里面直接使用sql函数的方法)
- python散点图(python scatter散点图用循环分类法加图例)
- python实现七个基本算法(python实现维吉尼亚算法)
- python多线程超时设置(解决python线程卡死的问题)
- python最简单实例(Python文件打开方式实例详解a、a+、r+、w+区别)
- python爬虫怎么爬取vip资源(Python网络爬虫之爬取微博热搜)
- python获取天气源(Python3爬虫之自动查询天气并实现语音播报)
- python基础教程常用函数整理(Python基础之函数的定义与使用示例)
- pythondict排序原理(Python标准库使用OrderedDict类的实例讲解)
- python 提取微信消息(python实现文件助手中查看微信撤回消息)
- python自动识别旋转验证码(Python实现字符型图片验证码识别完整过程详解)
- python 自定义获取文件目录(Python使用os.listdir和os.walk获取文件路径与文件下所有目录的方法)
- pythonpil安装包(基于Python的PIL库学习详解)
- python 怎么解析中文(Python中一般处理中文的几种方法)
- python字典的值排序(python 对字典按照value进行排序的方法)
- 夕云天际飞,亢龙化太极(夕云天际飞亢龙化太极)
- 爱情可以当饭吃吗(怎么回复)
- 高考数学题(高考数学题基础题占多少分)
- 没钱只能吃土(没钱要吃土了幽默短信发朋友圈)
- 今年考高会很难吗(今年高考会考试吗)
- 盘古开天地 他创造了世界,谁创造了盘古 盘古是伏羲吗(盘古开天地他创造了世界)
热门推荐
- vscode如何配置python环境(VSCode Python开发环境配置的详细步骤)
- sqlserver 创建数据库链接(SqlServer数据库远程连接案例教程)
- linux查看tcp状态(详解从Linux源码看SocketTCP的bind)
- css样式基础知识(CSS深入教程之文字修饰的那点事)
- 查看SQL SERVER指定数据库中所有的触发器
- python3web编程基础教程(python初学者,用python实现基本的学生管理系统python3代码实例)
- docker容器启动后秒退(解决docker run 或者 docker restart 启动镜像就自动退出)
- mysql定时任务
- php函数使用教程讲解(php函数式编程简单示例)
- laravel 快速开发api技巧(Laravel5.4简单实现app接口Api Token认证方法)
排行榜
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9