上篇文章我們對(duì)mpy標(biāo)準(zhǔn)微庫(kù)進(jìn)行了簡(jiǎn)單的方法羅列,，又因?yàn)閙py是從標(biāo)準(zhǔn)的Python庫(kù)中退化而來(lái)，那就先簡(jiǎn)單的學(xué)習(xí)一下Python的庫(kù),。

上面的文章說(shuō)了這么多,，那這篇就寫(xiě)這些

我這里就用3.8寫(xiě)了，使用jupyter環(huán)境

array是一個(gè)高效的數(shù)組模塊,，該模塊定義了一個(gè)對(duì)象類型,，它可以緊湊地表示一組基本值：字符、整數(shù),、浮點(diǎn)數(shù),。數(shù)組是序列類型，其行為與列表非常相似,，只是其中存儲(chǔ)的對(duì)象類型受到限制,。類型是在創(chuàng)建對(duì)象時(shí)使用類型代碼指定的， 類型代碼是單個(gè)字符,。定義了以下類型代碼：

筆記,，記好了

mpy中支持的格式代碼：b, B, h, H, i, I, l, L, q, Q, f, d（后 2 種取決于浮點(diǎn)支持）。

那這個(gè)和list有什么區(qū)別呢,？首先是一種序列類型,，序列方法都可以在上面使用。然后數(shù)組類型的對(duì)象是固定的,，不可以混合裝載

使用要先導(dǎo)入,，然后一開(kāi)始要指定存儲(chǔ)的數(shù)據(jù)類型

后面用元組傳入存儲(chǔ)的東西

IDE可以智能的給出方法

這里使用了一個(gè)列表的轉(zhuǎn)換方法

這個(gè)比較簡(jiǎn)單，實(shí)驗(yàn)了mpy提供的一個(gè)添加方法

請(qǐng)看extend的方法

array.extend(iterable)

將來(lái)自 iterable 的項(xiàng)添加到數(shù)組末尾,。如果 iterable 是另一個(gè)數(shù)組,，它必須具有 完全 相同的類型碼；否則將引發(fā) TypeError。如果 iterable 不是一個(gè)數(shù)組,，則它必須為可迭代對(duì)象并且其元素必須為可添加到數(shù)組的適當(dāng)類型,。

限制較多，其實(shí)數(shù)據(jù)類型相同就行,。其實(shí)方法這么少,，正好可以去看看實(shí)現(xiàn)，誰(shuí)說(shuō)不是呢,？

二進(jìn)制之間的轉(zhuǎn)換方法,，沒(méi)有什么說(shuō)的

復(fù)數(shù)運(yùn)算

這是完整的雙端隊(duì)列

mpy提供了兩個(gè)方法

我這里就做簡(jiǎn)單的演示

這些方法mpy不支持而且很多方法是之后才加進(jìn)來(lái)的

在看命名數(shù)組之前，需要知道一個(gè)概念,，叫工廠函數(shù)：

工廠函數(shù)看上去有點(diǎn)像函數(shù),，實(shí)質(zhì)上他們是類，當(dāng)你調(diào)用它們時(shí),，實(shí)際上是生成了該類型的一個(gè)實(shí)例,，就像工廠生產(chǎn)貨物一樣.

python核心編程

書(shū)籍的下載位置

書(shū)籍封面

當(dāng)然java里面也有這樣的概念，你可以看看

看這個(gè),，list這個(gè)函數(shù)本身就有工廠函數(shù)的能力

工廠函數(shù)是指這些內(nèi)建函數(shù)都是類對(duì)象,，當(dāng)你調(diào)用它們的時(shí)候，實(shí)際上是創(chuàng)建了一個(gè)類實(shí)例,，其實(shí)也可以理解成內(nèi)建函數(shù),。

歸根結(jié)底，它源于設(shè)計(jì)模式中的一種說(shuō)法,，就是指你不通過(guò)類來(lái)直接構(gòu)造對(duì)象,，而是通過(guò)一個(gè)函數(shù)來(lái)構(gòu)造對(duì)象，這樣允許你在函數(shù)中加入更多的控制,。

懵了嗎,？要是就這就懵了，那別看了~

其中命名元組賦予每個(gè)位置一個(gè)含義,，提供可讀性和自文檔性,。它們可以用于任何普通元組，并添加了通過(guò)名字獲取值的能力,，通過(guò)索引值也是可以的,。

我覺(jué)得你看例子就能看懂

其中有使用位置和關(guān)鍵字實(shí)參，可以像普通元組一樣去索引,，字段可以用命去訪問(wèn),，加入了__repr__的值方法,。

在mpy里面是這樣使用的：

命名元組實(shí)例沒(méi)有字典,，所以它們要更輕量，并且占用更小內(nèi)存。

我這個(gè)ordereddict真的不知道怎么翻譯了,，反正就是可以迭代的時(shí)候（就是打印的時(shí)候可以按照你加進(jìn)去的順序打?。?br>

它會(huì)返回一個(gè) dict 子類的實(shí)例，支持常用的 dict 方法,。Ordered Dict 是一種記錄鍵首次插入順序的 dict ,。如果新條目覆蓋現(xiàn)有條目，則原始插入位置保持不變,。刪除一個(gè)條目并重新插入它將把它移到末尾,。

這是標(biāo)準(zhǔn)Python庫(kù)

使用前記得初始化，以上為mpy

輸出

接下來(lái)是文章中最有技術(shù)含量的東西,，堆隊(duì)列算法,，這個(gè)東西講起來(lái)就有學(xué)術(shù)味道了，而且還需要補(bǔ)充一些知識(shí)才可以,。

容器：

在計(jì)算機(jī)科學(xué)中,，容器是一個(gè)類或數(shù)據(jù)結(jié)構(gòu)，其實(shí)例（運(yùn)行實(shí)體）是其他對(duì)象的集合,。換句話說(shuō),，它們以遵循特定訪問(wèn)規(guī)則的有組織的方式存儲(chǔ)對(duì)象。容器的大小取決于它包含的對(duì)象（元素）的數(shù)量,。各種容器類型的底層（繼承）實(shí)現(xiàn)的大小和復(fù)雜性可能不同,，并為任何給定場(chǎng)景選擇正確的實(shí)現(xiàn)提供了靈活性。

容器可以通過(guò)以下三個(gè)屬性來(lái)表征：

    1.access,，即訪問(wèn)容器對(duì)象的方式,。在數(shù)組的情況下，訪問(wèn)是通過(guò)數(shù)組索引完成的,。在堆棧的情況下,，根據(jù)LIFO（后進(jìn)先出）順序進(jìn)行訪問(wèn)，而在隊(duì)列的情況下,，根據(jù)FIFO（先進(jìn)先出）順序進(jìn)行訪問(wèn),；

    2.storage，即容器對(duì)象的存儲(chǔ)方式,；

    3.traversal,，即遍歷容器對(duì)象的方式。

容器類應(yīng)該實(shí)現(xiàn)方法來(lái)執(zhí)行以下操作：

    1.創(chuàng)建一個(gè)空容器（構(gòu)造函數(shù)）,；

    2.將對(duì)象插入容器,；

    3.從容器中刪除對(duì)象；

    4.刪除容器中的所有對(duì)象（清除）,；

    5.訪問(wèn)容器中的對(duì)象,；

    6.訪問(wèn)容器中的對(duì)象數(shù)量（計(jì)數(shù)）,。

    7.容器有時(shí)與迭代器一起實(shí)現(xiàn)。

注意,，容器其實(shí)是一種組織形式,，就是特定的操作定義。它不單單是一種數(shù)據(jù)結(jié)構(gòu),，它是一種更加高層的對(duì)數(shù)據(jù)結(jié)構(gòu)的表達(dá),。

堆又是屬于隊(duì)列這種結(jié)構(gòu)：

在計(jì)算機(jī)科學(xué)中，隊(duì)列是按序列維護(hù)的實(shí)體集合,，可以通過(guò)在序列的一端添加實(shí)體和從序列的另一端刪除實(shí)體來(lái)修改,。按照慣例，添加元素的序列末尾稱為隊(duì)列的后部,、尾部或后部,，刪除元素的末尾稱為隊(duì)列的頭部或前部，類似于以下使用的詞人們排隊(duì)等候商品或服務(wù),。

將元素添加到隊(duì)列尾部的操作稱為入隊(duì),，而從隊(duì)列中移除元素的操作稱為出隊(duì)。也可能允許其他操作,，通常包括查看或前端操作,，該操作返回下一個(gè)要出隊(duì)的元素的值而不將其出隊(duì)。

隊(duì)列的操作使其成為先進(jìn)先出 (FIFO) 數(shù)據(jù)結(jié)構(gòu),。在 FIFO 數(shù)據(jù)結(jié)構(gòu)中,，添加到隊(duì)列的第一個(gè)元素將是第一個(gè)被刪除的元素。這相當(dāng)于要求一旦添加了新元素,，必須先刪除之前添加的所有元素,，然后才能刪除新元素。隊(duì)列是線性數(shù)據(jù)結(jié)構(gòu)的一個(gè)例子,，或者更抽象地說(shuō)是一個(gè)順序集合,。隊(duì)列在計(jì)算機(jī)程序中很常見(jiàn)，它們被實(shí)現(xiàn)為與訪問(wèn)例程耦合的數(shù)據(jù)結(jié)構(gòu),、抽象數(shù)據(jù)結(jié)構(gòu)或在面向?qū)ο蟮恼Z(yǔ)言中作為類,。常見(jiàn)的實(shí)現(xiàn)是循環(huán)緩沖區(qū)和鏈表。

隊(duì)列在計(jì)算機(jī)科學(xué),、傳輸和運(yùn)籌學(xué)領(lǐng)域提供服務(wù),，其中存儲(chǔ)和保存各種實(shí)體（如數(shù)據(jù)、對(duì)象,、人員或事件）以供以后處理,。在這些上下文中，隊(duì)列執(zhí)行緩沖區(qū)的功能,。隊(duì)列的另一個(gè)用途是實(shí)現(xiàn)廣度優(yōu)先搜索,。

大O表示

這個(gè)東西算是最出名的東西

那我們的堆是隊(duì)列中的優(yōu)先級(jí)隊(duì)列：

在計(jì)算機(jī)科學(xué)中,，優(yōu)先級(jí)隊(duì)列是一種抽象數(shù)據(jù)類型，類似于常規(guī)隊(duì)列或堆棧數(shù)據(jù)結(jié)構(gòu),，其中每個(gè)元素還具有與其關(guān)聯(lián)的“優(yōu)先級(jí)”,。在優(yōu)先級(jí)隊(duì)列中,，優(yōu)先級(jí)高的元素在優(yōu)先級(jí)低的元素之前被服務(wù),。在某些實(shí)現(xiàn)中，如果兩個(gè)元素具有相同的優(yōu)先級(jí),，則根據(jù)它們?nèi)腙?duì)的順序?yàn)樗鼈兲峁┓?wù),，而在其他實(shí)現(xiàn)中，具有相同優(yōu)先級(jí)的元素的排序是不確定的,。

雖然優(yōu)先級(jí)隊(duì)列通常用堆實(shí)現(xiàn),，但它們?cè)诟拍钌吓c堆不同。優(yōu)先級(jí)隊(duì)列是一個(gè)類似于“列表”或“地圖”的概念,；正如列表可以用鏈表或數(shù)組實(shí)現(xiàn)一樣,，優(yōu)先隊(duì)列可以用堆或各種其他方法（例如無(wú)序數(shù)組）來(lái)實(shí)現(xiàn)。

上面這么多就夠了,，這里只說(shuō)一下,。堆是一種稱為優(yōu)先級(jí)隊(duì)列的抽象數(shù)據(jù)類型的最高效率實(shí)現(xiàn)，實(shí)際上,，優(yōu)先級(jí)隊(duì)列通常稱為“堆”,，無(wú)論它們?nèi)绾螌?shí)現(xiàn)。在堆中,，最高（或最低）優(yōu)先級(jí)的元素總是存儲(chǔ)在根,。但是，堆不是排序結(jié)構(gòu),；它可以被認(rèn)為是部分有序的,。當(dāng)需要重復(fù)刪除具有最高（或最低）優(yōu)先級(jí)的對(duì)象時(shí)，堆是一種有用的數(shù)據(jù)結(jié)構(gòu),。

一個(gè)圖解決戰(zhàn)斗,，看節(jié)點(diǎn)的數(shù)字大小

只實(shí)現(xiàn)了這三個(gè)

這個(gè)模塊提供了堆隊(duì)列算法的實(shí)現(xiàn)，也稱為優(yōu)先隊(duì)列算法,。

堆是一個(gè)二叉樹(shù),，它的每個(gè)父節(jié)點(diǎn)的值都只會(huì)小于或大于所有孩子節(jié)點(diǎn)。它使用了數(shù)組來(lái)實(shí)現(xiàn)：從零開(kāi)始計(jì)數(shù),，對(duì)于所有的 k ,，都有``heap[k] <= heap[2*k+1]`` 和 heap[k] <= heap[2*k+2] 。為了便于比較,，不存在的元素被認(rèn)為是無(wú)限大,。堆最有趣的特性在于最小的元素總是在根結(jié)點(diǎn)：heap[0] ,。

這個(gè)API與教材中堆算法的實(shí)現(xiàn)不太一樣，在于兩方面：

（a）我們使用了基于零開(kāi)始的索引,。這使得節(jié)點(diǎn)和其孩子節(jié)點(diǎn)之間的索引關(guān)系不太直觀,，但是由于Python使用了從零開(kāi)始的索引，所以這樣做更加合適,。

（b）我們的 pop 方法返回了最小的元素,，而不是最大的

（這在教材中叫做 “最小堆”；而“最大堆”在課本中更加常見(jiàn),，因?yàn)樗舆m用于原地排序）,。

基于這兩方面，把堆看作原生的Python list也沒(méi)什么奇怪的： heap[0] 表示最小的元素,，同時(shí) heap.sort() 維護(hù)了堆的不變性,！

注意堆的實(shí)現(xiàn)，是一個(gè)單獨(dú)的模塊

mpy中的堆操作,，之后在使用的時(shí)候做說(shuō)明