python学习笔记(十三)标准库heapq
heapq
堆(heap),是一種數(shù)據(jù)結(jié)構(gòu)。用維基百科中的說(shuō)明:
堆(英語(yǔ):heap),是計(jì)算機(jī)科學(xué)中一類(lèi)特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個(gè)可以被看做一棵樹(shù)的數(shù)組對(duì)象。
對(duì)于這個(gè)新的概念,讀者不要感覺(jué)心慌意亂或者恐懼,因?yàn)樗举|(zhì)上不是新東西,而是在我們已經(jīng)熟知的知識(shí)基礎(chǔ)上的擴(kuò)展。
堆的實(shí)現(xiàn)是通過(guò)構(gòu)造二叉堆,也就是一種二叉樹(shù)。
基本知識(shí)
這是一顆在蘇州很常見(jiàn)的香樟樹(shù),馬路兩邊、公園里隨處可見(jiàn)。
但是,在編程中,我們常說(shuō)的樹(shù)通常不是上圖那樣的,而是這樣的:
跟真實(shí)現(xiàn)實(shí)生活中看到的樹(shù)反過(guò)來(lái),也就是“根”在上面。為什么這樣呢?我想主要是畫(huà)著更方便吧。但是,我覺(jué)這棵樹(shù),是完全寫(xiě)實(shí)的作品。我本人做為一名隱姓埋名多年的抽象派畫(huà)家,不喜歡這樣的樹(shù),我畫(huà)出來(lái)的是這樣的:
這棵樹(shù)有兩根枝杈,可不要小看這兩根枝杈哦,《道德經(jīng)》上不是說(shuō)“一生二,二生三,三生萬(wàn)物”。一就是下面那個(gè)干,二就是兩個(gè)枝杈,每個(gè)枝杈還可以看做下一個(gè)一,然后再有兩個(gè)枝杈,如此不斷重復(fù)(這簡(jiǎn)直就是遞歸呀),就成為了一棵大樹(shù)。
我的確很佩服我自己的后現(xiàn)代抽象派的作品。但是,我更喜歡把這棵樹(shù)畫(huà)成這樣:
并且給它一個(gè)正規(guī)的名字:二叉樹(shù)
這個(gè)也是二叉樹(shù),完全脫胎于我所畫(huà)的后現(xiàn)代抽象主義作品。但是略有不同,這幅圖在各個(gè)枝杈上顯示的是數(shù)字。這種類(lèi)型的“樹(shù)”就編程語(yǔ)言中所說(shuō)的二叉樹(shù),維基百科曰:
在計(jì)算機(jī)科學(xué)中,二叉樹(shù)(英語(yǔ):Binary tree)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。通常子樹(shù)被稱作「左子樹(shù)」(left subtree)和「右子樹(shù)」(right subtree)。二叉樹(shù)常被用於實(shí)現(xiàn)二叉查找樹(shù)和二叉堆。
在上圖的二叉樹(shù)中,最頂端的那個(gè)數(shù)字就相當(dāng)于樹(shù)根,也就稱作“根”。每個(gè)數(shù)字所在位置成為一個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)向下分散出兩個(gè)“子節(jié)點(diǎn)”。就上圖的二叉樹(shù),在最后一層,并不是所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn),這類(lèi)二叉樹(shù)又稱為完全二叉樹(shù)(Complete Binary Tree),也有的二叉樹(shù),所有的節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn),這類(lèi)二叉樹(shù)稱作滿二叉樹(shù)(Full Binarry Tree),如下圖:
下面討論的對(duì)象是實(shí)現(xiàn)二叉堆就是通過(guò)二叉樹(shù)實(shí)現(xiàn)的。其應(yīng)該具有如下特點(diǎn):
- 節(jié)點(diǎn)的值大于等于(或者小于等于)任何子節(jié)點(diǎn)的值。
- 節(jié)點(diǎn)左子樹(shù)和右子樹(shù)是一個(gè)二叉堆。如果父節(jié)點(diǎn)的值總大于等于任何一個(gè)子節(jié)點(diǎn)的值,其為最大堆;若父節(jié)點(diǎn)值總小于等于子節(jié)點(diǎn)值,為最小堆。上面圖示中的完全二叉樹(shù),就表示一個(gè)最小堆。
堆的類(lèi)型還有別的,如斐波那契堆等,但很少用。所以,通常就將二叉堆也說(shuō)成堆。下面所說(shuō)的堆,就是二叉堆。而二叉堆又是用二叉樹(shù)實(shí)現(xiàn)的。
堆的存儲(chǔ)
堆用列表(有的語(yǔ)言中成為數(shù)組)來(lái)表示。如下圖所示:
從圖示中可以看出,將邏輯結(jié)構(gòu)中的樹(shù)的節(jié)點(diǎn)數(shù)字依次填入到存儲(chǔ)結(jié)構(gòu)中。看這個(gè)圖,似乎是列表中按照順序進(jìn)行排列似的。但是,這僅僅由于那個(gè)樹(shù)的特點(diǎn)造成的,如果是下面的樹(shù):
如果將上面的邏輯結(jié)構(gòu)轉(zhuǎn)換為存儲(chǔ)結(jié)構(gòu),讀者就能看出來(lái)了,不再是按照順序排列的了。
關(guān)于堆的各種,如插入、刪除、排序等,本節(jié)不會(huì)專(zhuān)門(mén)講授編碼方法,讀者可以參與有關(guān)資料。但是,下面要介紹如何用 Python 中的模塊 heapq 來(lái)實(shí)現(xiàn)這些操作。
heapq 模塊
heapq 中的 heap 是堆,q 就是 queue(隊(duì)列)的縮寫(xiě)。此模塊包括:
>>> import heapq >>> heapq.__all__ ['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop']依次查看這些函數(shù)的使用方法。
heappush(heap, x):將 x 壓入對(duì) heap(這是一個(gè)列表)
Help on built-in function heappush in module _heapq:heappush(...)heappush(heap, item) -> None. Push item onto heap, maintaining the heap invariant.>>> import heapq >>> heap = [] >>> heapq.heappush(heap, 3) >>> heapq.heappush(heap, 9) >>> heapq.heappush(heap, 2) >>> heapq.heappush(heap, 4) >>> heapq.heappush(heap, 0) >>> heapq.heappush(heap, 8) >>> heap [0, 2, 3, 9, 4, 8]請(qǐng)讀者注意我上面的操作,在向堆增加數(shù)值的時(shí)候,我并沒(méi)有嚴(yán)格按照什么順序,是隨意的。但是,當(dāng)我查看堆的數(shù)據(jù)時(shí),顯示給我的是一個(gè)有一定順序的數(shù)據(jù)結(jié)構(gòu)。這種順序不是按照從小到大,而是按照前面所說(shuō)的完全二叉樹(shù)的方式排列。顯示的是存儲(chǔ)結(jié)構(gòu),可以把它還原為邏輯結(jié)構(gòu),看看是不是一顆二叉樹(shù)。
由此可知,利用 heappush() 函數(shù)將數(shù)據(jù)放到堆里面之后,會(huì)自動(dòng)按照二叉樹(shù)的結(jié)構(gòu)進(jìn)行存儲(chǔ)。
heappop(heap):刪除最小元素
承接上面的操作:
>>> heapq.heappop(heap) 0 >>> heap [2, 4, 3, 9, 8]用 heappop() 函數(shù),從 heap 堆中刪除了一個(gè)最小元素,并且返回該值。但是,這時(shí)候的 heap 顯示順序,并非簡(jiǎn)單地將 0 去除,而是按照完全二叉樹(shù)的規(guī)范重新進(jìn)行排列。
heapify():將列表轉(zhuǎn)換為堆
如果已經(jīng)建立了一個(gè)列表,利用 heapify() 可以將列表直接轉(zhuǎn)化為堆。
>>> hl = [2, 4, 6, 8, 9, 0, 1, 5, 3] >>> heapq.heapify(hl) >>> hl [0, 3, 1, 4, 9, 6, 2, 5, 8]經(jīng)過(guò)這樣的操作,列表 hl 就變成了堆(注意觀察堆的順序,和列表不同),可以對(duì) hl(堆)使用 heappop() 或者 heappush() 等函數(shù)了。否則,不可。
>>> heapq.heappop(hl) 0 >>> heapq.heappop(hl) 1 >>> hl [2, 3, 5, 4, 9, 6, 8] >>> heapq.heappush(hl, 9) >>> hl [2, 3, 5, 4, 9, 6, 8, 9]不要認(rèn)為堆里面只能放數(shù)字,之所以用數(shù)字,是因?yàn)閷?duì)它的邏輯結(jié)構(gòu)比較好理解。
>>> heapq.heappush(hl, "q") >>> hl [2, 3, 5, 4, 9, 6, 8, 9, 'q'] >>> heapq.heappush(hl, "w") >>> hl [2, 3, 5, 4, 9, 6, 8, 9, 'q', 'w']heapreplace()
是 heappop() 和 heappush() 的聯(lián)合,也就是刪除一個(gè),同時(shí)加入一個(gè)。例如:
>>> heap [2, 4, 3, 9, 8] >>> heapq.heapreplace(heap, 3.14) 2 >>> heap [3, 4, 3.14, 9, 8]先簡(jiǎn)單羅列關(guān)于對(duì)的幾個(gè)常用函數(shù)。那么堆在編程實(shí)踐中的用途在哪方面呢?主要在排序上。一提到排序,讀者肯定想到的是 sorted() 或者列表中的 sort(),不錯(cuò),這兩個(gè)都是常用的函數(shù),而且在一般情況下已經(jīng)足夠使用了。如果再使用堆排序,相對(duì)上述方法應(yīng)該有優(yōu)勢(shì)。
堆排序的優(yōu)勢(shì)不僅更快,更重要的是有效地使用內(nèi)存,當(dāng)然,另外一個(gè)也不同忽視,就是簡(jiǎn)單易用。比如前面操作的,刪除數(shù)列中最小的值,就是在排序基礎(chǔ)上進(jìn)行的操作。
deque 模塊
有這樣一個(gè)問(wèn)題:一個(gè)列表,比如是[1,2,3],我打算在最右邊增加一個(gè)數(shù)字。
這也太簡(jiǎn)單了,不就是用 append() 這個(gè)內(nèi)建函數(shù),追加一個(gè)嗎?
這是簡(jiǎn)單,我要得寸進(jìn)尺,能不能在最左邊增加一個(gè)數(shù)字呢?
這個(gè)嘛,應(yīng)該有辦法。不過(guò)得想想了。讀者在向下閱讀的時(shí)候,能不能想出一個(gè)方法來(lái)?
>>> lst = [1, 2, 3] >>> lst.append(4) >>> lst [1, 2, 3, 4] >>> nl = [7] >>> nl.extend(lst) >>> nl [7, 1, 2, 3, 4]你或許還有別的方法。但是,Python 為我們提供了一個(gè)更簡(jiǎn)單的模塊,來(lái)解決這個(gè)問(wèn)題。
>>> from collections import deque這次用這種引用方法,因?yàn)?collections 模塊中東西很多,我們只用到 deque。
>>> lst [1, 2, 3, 4]還是這個(gè)列表。試試分別從右邊和左邊增加數(shù)
>>> qlst = deque(lst)這是必須的,將列表轉(zhuǎn)化為 deque。deque 在漢語(yǔ)中有一個(gè)名字,叫做“雙端隊(duì)列”(double-ended queue)。
>>> qlst.append(5) #從右邊增加 >>> qlst deque([1, 2, 3, 4, 5]) >>> qlst.appendleft(7) #從左邊增加 >>> qlst deque([7, 1, 2, 3, 4, 5])這樣操作多么容易呀。繼續(xù)看刪除:
>>> qlst.pop() 5 >>> qlst deque([7, 1, 2, 3, 4]) >>> qlst.popleft() 7 >>> qlst deque([1, 2, 3, 4])刪除也分左右。下面這個(gè),請(qǐng)讀者仔細(xì)觀察,更有點(diǎn)意思。
>>> qlst.rotate(3) >>> qlst deque([2, 3, 4, 1])rotate() 的功能是將[1, 2, 3, 4]的首位連起來(lái),你就想象一個(gè)圓環(huán),在上面有 1,2,3,4 幾個(gè)數(shù)字。如果一開(kāi)始正對(duì)著你的是 1,依順時(shí)針?lè)较蚺帕?#xff0c;就是從 1 開(kāi)始的數(shù)列,如下圖所示:
經(jīng)過(guò) rotate(),這個(gè)環(huán)就發(fā)生旋轉(zhuǎn)了,如果是 rotate(3),表示每個(gè)數(shù)字按照順時(shí)針?lè)较蚯斑M(jìn)三個(gè)位置,于是變成了:
請(qǐng)?jiān)徫业暮蟋F(xiàn)代注意超級(jí)抽象派作圖方式。從圖中可以看出,數(shù)列變成了[2, 3, 4, 1]。rotate() 作用就好像在撥轉(zhuǎn)這個(gè)圓環(huán)。
>>> qlst deque([3, 4, 1, 2]) >>> qlst.rotate(-1) >>> qlst deque([4, 1, 2, 3])如果參數(shù)是復(fù)數(shù),那么就逆時(shí)針轉(zhuǎn)。
在 deque 中,還有 extend 和 extendleft 方法。讀者可自己調(diào)試。
總結(jié)
以上是生活随笔為你收集整理的python学习笔记(十三)标准库heapq的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇: python学习笔记(十二)标准库os
- 下一篇: python学习笔记(十四)标准库url