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++有点区别。
这篇文档参考：参考文档
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
3月27日消息，苹果宣布2024年全球开发者大会（WWDC）将于6月10日至6月14日举行，巧合的是，这次大会与端午假期重合。
苹果官方表示：
在线参加 Apple 每年规模最大的开发者盛会。亲眼见证 Apple 最新平台、技术和工具的发布。了解如何创建和改进你的 App 和游戏。与 Apple 设计师和工程师互动交流，与全球开发者社区建立联系。以上活动均免费在线举行。
探索各种新的工具、框架和功能，助力你打造出理想的 App 和游戏。通过视频讲座学习新技能，与 Apple 专家进行一对一会面，以推进你的项目，完善你的构思。
Swift Student Challenge 旨在支持和鼓舞下一代开发者、创作者和企业家。太平洋时间 3 月 28 日，我们将公布今年的获奖者名单。获奖者将有资格参加在 Apple Park 举办的特别活动。我们还会选出 50 名杰出获胜者，他们将受邀前往库比提诺，获得为期三天的非凡体验，包括参加 Apple Park 的特别活动。
RTX 5090要首发 性能要翻倍！三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB，每个模块容量为2GB。其速度预设为32 Gbps（PAM3），但也可以降至28 Gbps，以提高产量和初始阶段的整体性能和成本效益。
据三星表示，GDDR7内存的能效将提高20%，同时工作电压仅为1.1V，低于标准的1.2V。通过采用更新的封装材料和优化的电路设计，使得在高速运行时的发热量降低，GDDR7的热阻比GDDR6降低了70%。