亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

PyTips 0x10 - Python 的堆與優(yōu)先隊列

dreambei / 2324人閱讀

摘要：項目地址中內置的庫和分別提供了堆和優(yōu)先隊列結構，其中優(yōu)先隊列本身也是基于實現的，因此我們這次重點看一下。堆可以用于實現調度器例見之協程，更常用的是優(yōu)先隊列例如。

項目地址：https://git.io/pytips

Python 中內置的 heapq 庫和 queue 分別提供了堆和優(yōu)先隊列結構，其中優(yōu)先隊列 queue.PriorityQueue 本身也是基于 heapq 實現的，因此我們這次重點看一下 heapq。

堆（Heap）是一種特殊形式的完全二叉樹，其中父節(jié)點的值總是大于子節(jié)點，根據其性質，Python 中可以用一個滿足 heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] 的列表來實現（heapq 也確實是這么做的）。堆可以用于實現調度器（例見：Python 3.5 之協程），更常用的是優(yōu)先隊列（例如：ImageColorTheme）。

heapq 提供了下面這些方法：

import heapq
print(heapq.__all__)
["heappush", "heappop", "heapify", "heapreplace", "merge", "nlargest", "nsmallest", "heappushpop"]

由于 Heap 是通過列表實現的，我們可以直接用列表創(chuàng)建：

from heapq import *
heap = []
heappush(heap, 3)
heappush(heap, 2)
heappush(heap, 1)
print(heap)
[1, 3, 2]
pop 或 sort 前要確保 heapify

或者通過 heapify 將普通列表轉化為 Heap：

heap = list(reversed(range(5)))
print("List: ", heap)
heapify(heap)
print("Heap: ", heap)
List:  [4, 3, 2, 1, 0]
Heap:  [0, 1, 2, 4, 3]

每次從 Heap 中 pop 出來的元素都是最小的（因而可以據此實現堆排序）：

heap = [5,4,3,2,1]
heapify(heap)
print(heappop(heap))
print(heappop(heap))
print(heappop(heap))
1
2
3
優(yōu)先隊列

queue.PriorityQueue 實際上只是對 heapq 的簡單封裝，直接使用其 heappush/heappop 方法：

from queue import PriorityQueue as PQueue
pq = PQueue()
pq.put((5 * -1, "Python"))
pq.put((4 * -1, "C"))
pq.put((3 * -1, "Js"))
print("Inside PriorityQueue: ", pq.queue) # 內部存儲
while not pq.empty():
    print(pq.get()[1])
Inside PriorityQueue:  [(-5, "Python"), (-4, "C"), (-3, "Js")]
Python
C
Js

由于 heapq 是最小堆，而通常 PriorityQueue 用在較大有限制的排前面，所以需要給 priority * -1。

sorted 一定是 Heap，反之未必

需要注意的是，雖然 Heap 通過 List 實習，但未經過 heapify() 處理的仍然是一個普通的 List，而 heappush 和 heappop 操作每次都會對 Heap 進行重新整理。此外，一個 Heap 列表不一定是正確排序的，但是經過 list.sort() 的列表一定是 Heap：

import random
lst = [random.randrange(1, 100) for _ in range(5)]
lst.sort()
print("List: ", lst)
print("Poped: ", heappop(lst))
heappush(lst, 4)
print("Heap: ", lst)
List:  [24, 55, 81, 83, 87]
Poped:  24
Heap:  [4, 55, 81, 87, 83]
最大/最小的 N 個數

Heap 還提供了 nsmallest 和 nlargest 方法用于取出前 n 個最大/最小數：

heap = [random.randrange(1, 1000) for _ in range(1000)]
heapify(heap)
print("N largest: ", nlargest(10, heap))
print("N smallest: ", nsmallest(10, heap))
print(len(heap))  # 不原地修改
N largest:  [999, 999, 998, 994, 992, 991, 990, 988, 985, 982]
N smallest:  [1, 1, 1, 2, 4, 5, 5, 6, 6, 9]
1000
合并（排序）

merge 方法用于將兩個 Heap 進行合并：

heapA = sorted([random.randrange(1, 100) for _ in range(3)])
heapB = sorted([random.randrange(1, 100) for _ in range(3)])

merged = []
for i in merge(heapA, heapB):
    merged.append(i)
print(merged)
[5, 29, 66, 66, 70, 99]

最后兩個方法 heapreplace 和 heappushpop 分別相當于：

lstA = [1,2,3,4,5]
lstB = [1,2,3,4,5]

poped = heapreplace(lstA, 0)
print("lstA: ", lstA, "poped: ", poped)

# is equal to...
poped = heappop(lstB)
heappush(lstB, 0)
print("lstB: ", lstA, "poped: ", poped)

print("*"*30)

poped = heappushpop(lstA, 9)
print("lstA: ", lstA, "poped: ", poped)

# is equal to...
heappush(lstB, 9)
poped = heappop(lstB)
print("lstB: ", lstB, "poped: ", poped)
lstA:  [0, 2, 3, 4, 5] poped:  1
lstB:  [0, 2, 3, 4, 5] poped:  1
******************************
lstA:  [2, 4, 3, 9, 5] poped:  0
lstB:  [2, 4, 3, 5, 9] poped:  0

這兩個方法的執(zhí)行效率要比分開寫的方法高，但要注意 heapreplace 要取代的值是否比 heap[0] 大，如果不是，可以用更有效的方法：

item = 0
lstA = [1,2,3,4,5]
if item < lstA[0]:
    # replace
    poped = lstA[0]
    lstA[0] = item
    print("lstA: ", lstA, "poped: ", poped)
lstA:  [0, 2, 3, 4, 5] poped:  1

歡迎關注公眾號 PyHub！

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://www.ezyhdfw.cn/yun/37859.html

相關文章

  • PHP面試：說下什么是堆和堆排序？

    摘要：一個常見的例子就是優(yōu)先隊列，還有排序算法之一的堆排序。另外我們還將學習堆排序，并將使用實現堆。堆排序在堆排序中，我們需要用給定的值構建一個一個堆。偽代碼如下從上面的偽代碼可以看到，堆排序的第一步就是構建一個堆。 堆是什么？ 堆是基于樹抽象數據類型的一種特殊的數據結構，用于許多算法和數據結構中。一個常見的例子就是優(yōu)先隊列，還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆...

    twohappy 評論0 收藏0

  • 堆與棧

    摘要：堆與棧棧由編譯器自動分配存放函數的參數值局部變量的值等其操作方式類似于數據結構中的棧堆一般由程序員分配釋放若程序員不釋放程序結束時可能由回收這里是指操作系統區(qū)別和聯系申請方式堆由程序員自己申請并指明大小在語言中的函數棧由系統自動分配聲明在函 堆與棧 棧(stack): 由編譯器自動分配, 存放函數的參數值, 局部變量的值等. 其操作方式類似于數據結構中的棧. 堆(heap): 一般由...

    April 評論0 收藏0

  • PyTips 0x13 - Python 線程與協程（2）

    摘要：項目地址我之前翻譯了協程原理這篇文章之后嘗試用了模式下的協程進行異步開發(fā)，確實感受到協程所帶來的好處至少是語法上的。 項目地址：https://git.io/pytips 我之前翻譯了Python 3.5 協程原理這篇文章之后嘗試用了 Tornado + Motor 模式下的協程進行異步開發(fā)，確實感受到協程所帶來的好處（至少是語法上的:D）。至于協程的 async/await 語法是如...

    史占廣 評論0 收藏0

  • PyTips 0x05 - Python 函數參數與解包

    摘要：這里的關鍵詞函數必須明確指明，不能通過位置推斷則代表任意數量的關鍵詞參數添加的新特性，使得可以在函數參數之外使用這里的逗號不能漏掉所謂的解包實際上可以看做是去掉的元組或者是去掉的字典。 項目地址：https://git.io/pytips 函數調用的參數規(guī)則與解包 Python 的函數在聲明參數時大概有下面 4 種形式： 不帶默認值的：def func(a): pass 帶有默認值的...

    pubdreamcc 評論0 收藏0

  • PyTips 0x 12 - Python 線程與協程（1）

    摘要：中關于線程的標準庫是，之前在版本中的在之后更名為，無論是還是都應該盡量避免使用較為底層的而應該使用。而與線程相比，協程尤其是結合事件循環(huán)無論在編程模型還是語法上，看起來都是非常友好的單線程同步過程。 項目地址：https://git.io/pytips 要說到線程（Thread）與協程（Coroutine）似乎總是需要從并行（Parallelism）與并發(fā)（Concurrency）談起...

    el09xccxy 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<