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個數，可以指定比較的keyheapq.nlargest(n, iterable[, key])#從可迭代的迭代器中返回最小的n個數，可以指定比較的keyheapq.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.0except 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++有點區別。
這篇文檔參考：參考文檔
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網。
新聞熱點
疑難解答
