python中heapq堆排算法的實(shí)現(xiàn)

第python中heapq堆排算法的實(shí)現(xiàn)目錄一、創(chuàng)建堆二、訪問(wèn)堆內(nèi)容三、獲取堆最大或最小值四、heapq應(yīng)用

一、創(chuàng)建堆

heapq有兩種方式創(chuàng)建堆，一種是使用一個(gè)空列表，然后使用heapq.heappush()函數(shù)把值加入堆中，另外一種就是使用heap.heapify(list)轉(zhuǎn)換列表成為堆結(jié)構(gòu)

importheapq

#第一種

函數(shù)定義：

heapq.heappush(heap,item)

-Pushthevalueitemontotheheap,maintainingtheheapinvariant.

heapq.heappop(heap)

-Popandreturnthesmallestitemfromtheheap,maintainingtheheapinvariant.

Iftheheapisempty,IndexErrorisraised.Toaccessthesmallestitemwithoutpoppingit,useheap[0].

nums=[2,3,5,1,54,23,132]

heap=[]

fornuminnums:

heapq.heappush(heap,num)#加入堆

print(heap[0])#如果只是想獲取最小值而不是彈出，使用heap[0]

print([heapq.heappop(heap)for_inrange(len(nums))])#堆排序結(jié)果

#out:[1,2,3,5,23,54,132]

#第二種

nums=[2,3,5,1,54,23,132]

heapq.heapify(nums)

print([heapq.heappop(heap)for_inrange(len(nums))])#堆排序結(jié)果

#out:[1,2,3,5,23,54,132]

heapq模塊還有一個(gè)??heapq.merge(*iterables)??方法，用于合并多個(gè)排序后的序列成一個(gè)排序后的序列，返回排序后的值的迭代器。

類似于??sorted(itertools.chain(*iterables))??，但返回的是可迭代的。

"""

函數(shù)定義：

heapq.merge(*iterables)

-Mergemultiplesortedinputsintoasinglesortedoutput(forexample,mergetimestampedentriesfrommultiplelogfiles).Returnsan

iteratoroverthesortedvalues.

-Similartosorted(itertools.chain(*iterables))butreturnsaniterable,doesnotpullthedataintomemoryallatonce,andassumes

thateachoftheinputstreamsisalreadysorted(smallesttolargest).

importheapq

num1=[32,3,5,34,54,23,132]

num2=[23,2,12,656,324,23,54]

num1=sorted(num1)

num2=sorted(num2)

res=heapq.merge(num1,num2)

print(list(res))

二、訪問(wèn)堆內(nèi)容

堆創(chuàng)建好后，可以通過(guò)`heapq.heappop()函數(shù)彈出堆中最小值。

importheapq

nums=[2,43,45,23,12]

heapq.heapify(nums)

print(heapq.heappop(nums))

#out:2

#如果需要所有堆排序后的元素

result=[heapq.heappop(nums)for_inrange(len(nums))]

print(result)

#out:[12,23,43,45]

如果需要?jiǎng)h除堆中最小元素并加入一個(gè)元素，可以使用??heapq.heaprepalce()??函數(shù)

importheapq

nums=[1,2,4,5,3]

heapq.heapify(nums)

heapq.heapreplace(nums,23)

print([heapq.heappop(nums)for_inrange(len(nums))])

#out:[2,3,4,5,23]

三、獲取堆最大或最小值

如果需要獲取堆中最大或最小的范圍值，則可以使用??heapq.nlargest()???或??heapq.nsmallest()??函數(shù)

"""

函數(shù)定義：

heapq.nlargest(n,iterable[,key])?

-Returnalistwiththenlargestelementsfromthedatasetdefinedbyiterable.

-keyifprovided,specifiesafunctionofoneargumentthatisusedtoextractacomparisonkeyfromeachelementintheiterable:key=str.lower

-Equivalentto:sorted(iterable,key=key,reverse=True)[:n]

importheapq

nums=[1,3,4,5,2]

print(heapq.nlargest(3,nums))

print(heapq.nsmallest(3,nums))

[5,4,3]

[1,2,3]

"""

這兩個(gè)函數(shù)還接受一個(gè)key參數(shù)，用于dict或其他數(shù)據(jù)結(jié)構(gòu)類型使用

importheapq

frompprintimportpprint

portfolio=[

{'name':'IBM','shares':100,'price':91.1},

{'name':'AAPL','shares':50,'price':543.22},

{'name':'FB','shares':200,'price':21.09},

{'name':'HPQ','shares':35,'price':31.75},

{'name':'YHOO','shares':45,'price':16.35},

{'name':'ACME','shares':75,'price':115.65}

cheap=heapq.nsmallest(3,portfolio,key=lambdas:s['price'])

expensive=heapq.nlargest(3,portfolio,key=lambdas:s['price'])

pprint(cheap)

pprint(expensive)

[{'name':'YHOO','price':16.35,'shares':45},

{'name':'FB','price':21.09,'shares':200},

{'name':'HPQ','price':31.75,'shares':35}]

[{'name':'AAPL','price':543.22,'shares':50},

{'name':'ACME','price':115.65,'shares':75},

{'name':'IBM','price':91.1,'shares':100}]

"""

四、heapq應(yīng)用

實(shí)現(xiàn)heap堆排序算法：

defheapsort(iterable):

...h=[]

...forvalueiniterable:

...heappush(h,value)

...return[heappop(h)foriinrange(len(h))]

heapsort([1,3,5,7,9,2,4,6,8,0])

[0,1,2,3,4,5,6,7,8,9]

該算法和??sorted(iterable)??類似，但是它是不穩(wěn)定的。

堆的值可以是元組類型，可以實(shí)現(xiàn)對(duì)帶