python 堆和優(yōu)先隊列的使用詳解

更新時間：2019年03月05日 11:02:41 作者：LIUHUANUCAS

這篇文章主要介紹了python 堆和優(yōu)先隊列的使用詳解，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧

1.heapq

python里面的堆是通過在列表中維護(hù)堆的性質(zhì)實現(xiàn)的。這一點(diǎn)與C++中heap一系列的算法類似，底層是通過堆vector的維護(hù)獲取堆的性質(zhì)。

關(guān)于二叉樹

二叉樹的特點(diǎn)：

二叉樹是一種存儲數(shù)據(jù)元素的匯集數(shù)據(jù)結(jié)構(gòu)。

二叉樹最重要的性質(zhì)就是樹的高度和樹中可以容納的最大結(jié)點(diǎn)個數(shù)之間的關(guān)系。樹的高度類似于表長，是從根結(jié)點(diǎn)到其他結(jié)點(diǎn)的最大距離。在長為n的表里只能容納n個結(jié)點(diǎn)，而在高為h的二叉樹中則可以容納大約2^h個結(jié)點(diǎn)，這是表和樹的最大不同點(diǎn)。

一般的元素插入，如果是按線性順序排列的，那么操作必然需要O(n)的時間(需要對n個數(shù)據(jù)進(jìn)行移位處理),要突破這個限制，必須考慮其他數(shù)據(jù)結(jié)構(gòu)的組織方式。二叉樹就是一種高效插入的存儲方式。

堆排序利用的是完全二叉樹。

python堆的部分API，其他API查閱文檔python_heap_API和 heapq的源代碼

import heapq
#向堆中插入元素，heapq會維護(hù)列表heap中的元素保持堆的性質(zhì)
heapq.heappush(heap, item)
#heapq把列表x轉(zhuǎn)換成堆
heapq.heapify(x)
#從可迭代的迭代器中返回最大的n個數(shù)，可以指定比較的key
heapq.nlargest(n, iterable[, key])
#從可迭代的迭代器中返回最小的n個數(shù)，可以指定比較的key
heapq.nsmallest(n, iterable[, key])
#從堆中刪除元素，返回值是堆中最小或者最大的元素
heapq.heappop(heap)

1.1.內(nèi)置類型

從上述源代碼可以看出來，heapq使用的內(nèi)置的小于號，或者類的__lt__比較運(yùn)算來進(jìn)行比較。

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.元組類型

元素會默認(rèn)調(diào)用內(nèi)置比較函數(shù)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_，當(dāng)然沒有重寫但是有其他的比較函數(shù)例如：_le_,_gt_,_cmp_,也是會調(diào)用的，和小于號等價的都可以調(diào)用(測試了gt)，具體的這些操作之間的關(guān)系我也沒有研究過。如果類里面沒有重寫_lt_，會調(diào)用其他的比較操作符，從源代碼可以看出來，如果沒有_lt_，那么會調(diào)用_ge_函數(shù)。

所以可以重寫上述的那些函數(shù)：

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

所以如果要用到自己定義的類型，可以重寫上述函數(shù)，就可以使用heapq函數(shù)了。

2.PriorityQueue

PriorityQueue的python源代碼PriorityQueue

從源代碼可以看出來，PriorityQueue使用的就是heapq來實現(xiàn)的，所以可以認(rèn)為兩者算法本質(zhì)上是一樣的。當(dāng)然PriorityQueue考慮到了線程安全的問題。

下面給出PriorityQueue的部分API和使用方法。

參考Queue

#向隊列中添加元素
Queue.put(item[, block[, timeout]])
#從隊列中獲取元素
Queue.get([block[, timeout]])
#隊列判空
Queue.empty()
#隊列大小
Queue.qsize()

2.1.內(nèi)置類型

直接調(diào)用內(nèi)置函數(shù)cmp進(jìn)行比較

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

其他的一些方法的使用還是需要參考給出的文檔的。

最后一點(diǎn)，讓我比較奇怪的是（可能我并沒有找到），沒有提供像排序函數(shù)那樣，指定比較方法函數(shù)，這點(diǎn)和c++有點(diǎn)區(qū)別。

這篇文檔參考：參考文檔

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: