本文是對(duì) Swift Algorithm Club 翻譯的一篇文章。

Swift Algorithm Club是 raywenderlich.com網(wǎng)站出品的用Swift實(shí)現(xiàn)算法和數(shù)據(jù)結(jié)構(gòu)的開源項(xiàng)目，目前在GitHub上有18000+??，我初略統(tǒng)計(jì)了一下，大概有一百左右個(gè)的算法和數(shù)據(jù)結(jié)構(gòu)，基本上常見(jiàn)的都包含了，是iOSer學(xué)習(xí)算法和數(shù)據(jù)結(jié)構(gòu)不錯(cuò)的資源。

??andyRon/swift-algorithm-club-cn是我對(duì)Swift Algorithm Club，邊學(xué)習(xí)邊翻譯的項(xiàng)目。由于能力有限，如發(fā)現(xiàn)錯(cuò)誤或翻譯不妥，請(qǐng)指正，歡迎pull request。也歡迎有興趣、有時(shí)間的小伙伴一起參與翻譯和學(xué)習(xí)??。當(dāng)然也歡迎加??，??????????。

本文的翻譯原文和代碼可以查看??swift-algorithm-club-cn/Heap

堆(Heap)

這個(gè)話題已經(jīng)有個(gè)輔導(dǎo)文章

堆是數(shù)組內(nèi)的二叉樹，因此它不使用父/子指針。 堆基于“堆屬性”進(jìn)行排序，“堆屬性”確定樹中節(jié)點(diǎn)的順序。

堆的一般用途：

• 構(gòu)建優(yōu)先隊(duì)列。
• 支持堆排序。
• 快速計(jì)算集合中最大（或最?。┲?。
• 給你的非程序員朋友留下深刻影響。

堆屬性

有兩種堆：max-heap 和 min-heap，它們存儲(chǔ)樹節(jié)點(diǎn)的順序不同。

在max-heap中，每個(gè)父節(jié)點(diǎn)的值大于其子節(jié)點(diǎn)。 在min-heap中，每個(gè)父節(jié)點(diǎn)的值都小于其子節(jié)點(diǎn)。 這稱為“堆屬性”，對(duì)于樹中的每個(gè)節(jié)點(diǎn)都是如此。

一個(gè)例子：

A max-heap

這是一個(gè)max-heap，因?yàn)槊總€(gè)父節(jié)點(diǎn)都大于其子節(jié)點(diǎn)。 (10)大于(7)和(2)。 (7)大于(5)和(1)。

堆屬性的結(jié)果是，max-heap始終將其最大項(xiàng)存儲(chǔ)在樹的根節(jié)點(diǎn)中。 對(duì)于min-heap，根節(jié)點(diǎn)始終是樹中的最小項(xiàng)。 堆屬性很有用，因?yàn)槎淹ǔＳ米?a target="_blank" rel="nofollow">優(yōu)先隊(duì)列來(lái)快速訪問(wèn)“最重要的”（譯注：最大或最?。┰亍?/p>

注意： 堆的根節(jié)點(diǎn)是最大或最小元素，但其他元素的排序順序是不可預(yù)測(cè)的。例如，最大元素始終位于max-heap中的索引0處，但最小元素不一定是最后一個(gè)元素。 —— 唯一的保證是，最小元素是葉節(jié)點(diǎn)之一，但不知道是哪一個(gè)。

堆與常規(guī)樹對(duì)比

堆不是二叉搜索樹的替代品，它們之間存在相似之處和不同之處。 以下是一些主要差異：

節(jié)點(diǎn)的順序。在二叉搜索樹（BST）中，左子節(jié)點(diǎn)必須小于其父節(jié)點(diǎn)，右子節(jié)點(diǎn)必須更大。 堆不是這樣。 在max-heap中，兩個(gè)子節(jié)點(diǎn)必須小于父節(jié)點(diǎn)，而在min-heap中，子節(jié)點(diǎn)必須大于父節(jié)點(diǎn)。

內(nèi)存。傳統(tǒng)的樹比它們存儲(chǔ)的數(shù)據(jù)占用更多的內(nèi)存。 需要為節(jié)點(diǎn)對(duì)象和指向左/右子節(jié)點(diǎn)的指針?lè)峙漕~外的存儲(chǔ)空間。 堆只使用普通數(shù)組進(jìn)行存儲(chǔ)，不使用指針。

平衡。 二叉搜索樹（BST）必須“平衡”，以便大多數(shù)操作具有O(log n)性能。 您可以按隨機(jī)順序插入和刪除數(shù)據(jù)，也可以使用AVL樹或紅黑樹，但 我們實(shí)際上并不需要對(duì)整個(gè)樹進(jìn)行排序。 我們只是希望實(shí)現(xiàn)堆屬性，因此平衡不是問(wèn)題。 由于堆的結(jié)構(gòu)方式，堆可以保證 O(log n) 的性能。

搜索。 雖然在二叉樹中搜索速度很快，但在堆中搜索速度很慢。 搜索不是堆中的最高優(yōu)先級(jí)，因?yàn)槎训哪康氖菍⒆畲螅ɑ蜃钚。┕?jié)點(diǎn)放在前面并允許相對(duì)快速的插入和刪除。

數(shù)組中的樹

用數(shù)組實(shí)現(xiàn)樹狀結(jié)構(gòu)似乎比較奇怪，但它在時(shí)間和空間上都很高效的。

上面例子中的樹用數(shù)組存儲(chǔ)為：

[ 10, 7, 2, 5, 1 ]

這里的所有了！ 我們不需要比這個(gè)簡(jiǎn)單數(shù)組更多的存儲(chǔ)空間了。

那么，如果不允許使用任何指針，我們?nèi)绾沃滥男┕?jié)點(diǎn)是父節(jié)點(diǎn)，哪些節(jié)點(diǎn)是子節(jié)點(diǎn)？ 好問(wèn)題！樹節(jié)點(diǎn)的數(shù)組索引與其父節(jié)點(diǎn)和子節(jié)點(diǎn)的數(shù)組索引之間存在明確定義的關(guān)系。

如果i是節(jié)點(diǎn)的索引，則以下公式給出其父節(jié)點(diǎn)和子節(jié)點(diǎn)的數(shù)組索引：

parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2

注意right(i)只是left(i)+ 1。 左側(cè)和右側(cè)子節(jié)點(diǎn)始終緊挨著存儲(chǔ)。

對(duì)上面的例子使用這些公式。 填寫數(shù)組索引，我們應(yīng)該得到數(shù)組中父節(jié)點(diǎn)和子節(jié)點(diǎn)的位置：

驗(yàn)證這些數(shù)組索引確實(shí)對(duì)應(yīng)于上面樹的圖片。

注意： 根節(jié)點(diǎn)(10)沒(méi)有父節(jié)點(diǎn)，因?yàn)?code>-1不是有效的數(shù)組索引。 同樣，節(jié)點(diǎn)(2)，(5)和(1)沒(méi)有子節(jié)點(diǎn)，因?yàn)槟切┧饕笥跀?shù)組大小，所以用它們之前我們總是要確保我們計(jì)算的索引實(shí)際上是有效的。

回想一下，在max-heap中，父節(jié)點(diǎn)的值總是大于（或等于）其子節(jié)點(diǎn)的值。 這意味著對(duì)于所有數(shù)組索引i必須滿足以下條件：

array[parent(i)] >= array[I]

驗(yàn)證此堆屬性是否適用于示例堆中的數(shù)組。

如您所見(jiàn)，這些等式允許我們?cè)诓恍枰羔樀那闆r下找到任何節(jié)點(diǎn)的父索引或子索引。 這樣消除了使用指針的復(fù)雜，這是一種權(quán)衡：我們節(jié)省了內(nèi)存空間，但需要額外的計(jì)算。 幸運(yùn)的是，計(jì)算速度很快，只需要 O(1) 時(shí)間。

理解樹中數(shù)組索引和位置之間的這種關(guān)系很重要。 下面??是一個(gè)更大的堆，有15個(gè)節(jié)點(diǎn)分為四個(gè)級(jí)別：

Large Heap

此圖片中的數(shù)字不是節(jié)點(diǎn)的值，而是存儲(chǔ)節(jié)點(diǎn)的數(shù)組索引！ 下面??是數(shù)組索引對(duì)應(yīng)樹的不同級(jí)別：

The heap array

要使公式起作用，父節(jié)點(diǎn)必須出現(xiàn)在數(shù)組中的子節(jié)點(diǎn)之前。 你可以在上面的圖片中看到。

請(qǐng)注意，此方案有局限性。 您可以使用常規(guī)二叉樹執(zhí)行以下操作，但不能使用堆執(zhí)行以下操作：

Impossible with a heap

除非當(dāng)前最低級(jí)別已滿，否則無(wú)法開啟新級(jí)別，因此堆總是具有這種形狀：

注意： 您可以使用堆模擬常規(guī)二叉樹，但這會(huì)浪費(fèi)空間，您需要將一些數(shù)組索引標(biāo)記為空。

突擊測(cè)驗(yàn)！ 假設(shè)我們有數(shù)組：

[ 10, 14, 25, 33, 81, 82, 99 ]

這是一個(gè)有效的堆嗎？ 答案是肯定的！ 從低到高的排序數(shù)組是有效的min-heap。 我們可以按如下方式繪制這個(gè)堆：

堆屬性適用于每個(gè)節(jié)點(diǎn)，因?yàn)楦腹?jié)點(diǎn)始終小于其子節(jié)點(diǎn)。 （自己驗(yàn)證從高到低排序的數(shù)組始終是有效的max-heap。）

注意：但并非每個(gè)min-heap都必須是一個(gè)排序數(shù)組！ 排序數(shù)組只是一種特殊情況。 要將堆重新轉(zhuǎn)換為已排序的數(shù)組，需要使用堆排序。

更多數(shù)學(xué)！

如果你很好奇，這里有一些描述堆的某些屬性的公式。 你不需要知道這些，但它們有時(shí)會(huì)派上用場(chǎng)。 可以跳過(guò)此部分！

樹的height定義為從根節(jié)點(diǎn)到最低葉節(jié)點(diǎn)所需的步數(shù)，或者更正式：height是節(jié)點(diǎn)之間的最大邊數(shù)。 高度h的堆具有h + 1級(jí)別。

這個(gè)堆的高度為3，所以它有4個(gè)級(jí)別：

Large Heap

具有n個(gè)節(jié)點(diǎn)的堆具有高度h = floor(log2(n))。 這是因?yàn)槲覀兛偸窃谔砑有录?jí)別之前完全填滿最低級(jí)別。 該示例有15個(gè)節(jié)點(diǎn)，因此高度為 floor(log2(15)) = floor(3.91) = 3。

如果最低級(jí)別已滿，則該級(jí)別包含 2^h 個(gè)節(jié)點(diǎn)。 它上面的樹的其余部分包含 2^h - 1 個(gè)節(jié)點(diǎn)。 上面示例就是：最低級(jí)別有8個(gè)節(jié)點(diǎn)，實(shí)際上是 2^3 = 8 。 前三個(gè)級(jí)別包含總共7個(gè)節(jié)點(diǎn)，即2^3 - 1 = 8 - 1 = 7。

因此，整個(gè)堆中的節(jié)點(diǎn)總數(shù)n 為 2^(h+1) - 1。 在示例中，2^4 - 1 = 16 - 1 = 15。

在n個(gè)元素堆中，高度為h的最多有 ceil(n/2^(h+1)) 個(gè)的節(jié)點(diǎn)。（譯注：示例中h為0時(shí)，ceil(15/2^(0+1)) = 8，h為1時(shí),ceil(15/2^(1+1)) = 4）

葉節(jié)點(diǎn)總是位于數(shù)組索引 floor(n/2) 到 n-1。(譯注： 7 ~ 14) 我們將利用這一事實(shí)從數(shù)組中快速構(gòu)建堆。 如果您不相信，請(qǐng)驗(yàn)證此示例。;-)

只是一些數(shù)學(xué)就能照亮你的一天。??

你能用堆做什么？

在插入或刪除元素之后，有兩個(gè)必要的原始操作來(lái)確保堆是有效的max-heap或min-heap：

• shiftUp()：如果元素比其父元素更大（max-heap）或更?。?em>min-heap），則需要與父元素交換， 這使元素向上移動(dòng)。

• shiftDown()。 如果元素比子元素?。╩ax-heap）或更大（min-heap），這個(gè)操作使元素向下移動(dòng)，也稱為“堆化(heapify)”。

向上或向下移動(dòng)是一個(gè)遞歸過(guò)程，需要O(log n)時(shí)間。

以下是基于原始操作的其他操作：

• insert(value)：將新元素添加到堆的末尾，然后使用shiftUp()來(lái)修復(fù)堆。

• remove()：刪除并返回最大值(max-heap）或最小值(min-heap）。為了填充元素刪除后留下的位置，讓最后一個(gè)元素移動(dòng)到根位置，然后使用shiftDown()修復(fù)堆。 (有時(shí)稱為“提取最小值”或“提取最大值”。）

• removeAtIndex(index)：類似remove()，不僅可以刪除根節(jié)點(diǎn)，也可以從堆中刪除任何節(jié)點(diǎn)。如果新元素與其子元素不規(guī)整，則調(diào)用shiftDown();如果元素與其父元素不規(guī)整，則調(diào)用shiftUp()。

• replace(index, value)：為節(jié)點(diǎn)分配一個(gè)較小(min-heap）或較大(max-heap）的值。因?yàn)檫@會(huì)使堆屬性失效，所以它使用shiftUp()來(lái)修復(fù)。 (也稱為“減少鍵”和“增加鍵”。）

以上所有操作都需要時(shí)間O(log n)因?yàn)橄蛏匣蛳蛳乱苿?dòng)是昂貴的。還有一些操作需要更多時(shí)間：

• search(value)。堆不是為高效搜索而構(gòu)建的，但replace()和removeAtIndex()操作需要節(jié)點(diǎn)的數(shù)組索引，因此您需要找到該索引。時(shí)間：O(n)。

• buildHeap(array)：通過(guò)重復(fù)調(diào)用insert()將數(shù)組(未排序的）轉(zhuǎn)換為堆。如果您對(duì)此很聰明，可以在O(n)時(shí)間內(nèi)完成。

• 堆排序。由于堆是一個(gè)數(shù)組，我們可以使用它的唯一屬性將數(shù)組從低到高排序。時(shí)間：O(n lg n)。

堆還有一個(gè)peek()函數(shù)，它返回最大(max-heap）或最小(min-heap）元素，而不從堆中刪除它。時(shí)間：O(1)。

注意： 到目前為止，您將使用堆執(zhí)行的最常見(jiàn)操作是使用insert()插入新值，并使用remove()刪除最大值或最小值。 兩者都需要O(log n)時(shí)間。 其他操作用來(lái)支持更高級(jí)的使用，例如構(gòu)建優(yōu)先隊(duì)列，其中項(xiàng)目的“重要性”在添加到隊(duì)列后可以改變。

向堆中插入元素

我們來(lái)看一個(gè)插入示例，詳細(xì)了解其工作原理。 我們將值16插入此堆：

這個(gè)堆的數(shù)組是[10, 7, 2, 5, 1]。

插入新項(xiàng)目的第一步是將其附加到數(shù)組的末尾。 該數(shù)組變?yōu)椋?/p>

[ 10, 7, 2, 5, 1, 16 ]

樹結(jié)構(gòu)如下：

(16)被添加到最后一行的第一個(gè)可用空間。

不幸的是，堆屬性不再滿足，因?yàn)?code>(2)高于(16)，我們希望更高的數(shù)字高于低的數(shù)字。 (這是max-heap。)

要恢復(fù)堆屬性，我們交換(16)和(2)。

我們還沒(méi)有完成，因?yàn)?code>(10)也小于(16)。 我們繼續(xù)將其插入值與其父項(xiàng)交換，直到父項(xiàng)更大或到達(dá)樹的頂部。 這稱為shift-up 或 sifting ，并在每次插入后完成。 它會(huì)使一個(gè)太大或太小的數(shù)字“浮起”樹。

最后，我們得到：

現(xiàn)在每個(gè)父節(jié)點(diǎn)都比其子節(jié)點(diǎn)更大了。

上移所需的時(shí)間與樹的高度成正比，需要O(log n)時(shí)間。（將節(jié)點(diǎn)附加到數(shù)組末尾所需的時(shí)間僅為O(1)，因此不會(huì)降低它的速度。）

刪除根節(jié)點(diǎn)

從樹中移除(10)：

頂部的空白怎么辦？

插入時(shí)，我們將新值放在數(shù)組的末尾。 在這里，我們做相反的事情：我們采用我們擁有的最后一個(gè)對(duì)象，將其直接移動(dòng)到樹的頂部，然后恢復(fù)堆屬性。

讓我們來(lái)看看如何shift-down(1)。 要維護(hù)此max-heap的堆屬性，我們希望頂部為最大數(shù)。 我們有兩個(gè)交換位置的候選者：(7)和(2)。 選擇這三個(gè)節(jié)點(diǎn)之間的最高數(shù)字位于頂部，那是(7)，所以交換(1)和(7)，得到下面??的樹：

繼續(xù)向下移動(dòng)，直到節(jié)點(diǎn)沒(méi)有任何子節(jié)點(diǎn)，或者它比兩個(gè)子節(jié)點(diǎn)都大。 對(duì)于這個(gè)堆，只需要一個(gè)交換來(lái)恢復(fù)堆屬性：

完全向下移動(dòng)所需的時(shí)間與樹的高度成正比，這需要O(log n)時(shí)間。

注意： shiftUp()和shiftDown()一次只能修復(fù)一個(gè)異常元素。 如果錯(cuò)誤的位置有多個(gè)元素，則需要為每個(gè)元素調(diào)用一次這些函數(shù)。

刪除任意節(jié)點(diǎn)

絕大多數(shù)情況下，將刪除的是堆根節(jié)點(diǎn)，因?yàn)檫@是堆設(shè)計(jì)的目的。

但是，刪除任意元素可能很有用。 這是remove()的一般版本，可能涉及shiftDown()或shiftUp()。

讓我們?cè)俅尾捎们懊娴氖纠龢?，刪除(7)：

提醒一下，數(shù)組是：

[ 10, 7, 2, 5, 1 ]

如您所知，刪除元素可能會(huì)使max-heap或min-heap屬性失效。 要解決這個(gè)問(wèn)題，我們將要移除的節(jié)點(diǎn)與最后一個(gè)元素交換：

[ 10, 1, 2, 5, 7 ]

最后一個(gè)元素是我們將返回的元素; 我們將調(diào)用removeLast()將其從堆中刪除。 (1)現(xiàn)在是亂序的，因?yàn)樗∮谒淖庸?jié)點(diǎn)，(5)是在樹中應(yīng)該更高。 我們調(diào)用shiftDown()來(lái)修復(fù)它。

但是，向下移動(dòng)并不是我們需要處理的唯一情況。 也可能發(fā)生新元素必須向上移動(dòng)。 考慮如果從以下堆中刪除(5)會(huì)發(fā)生什么：

譯注：這個(gè)的樹對(duì)應(yīng)的數(shù)組是[10, 7, 9, 5, 1, 2, 8]。

現(xiàn)在(5)與(8)交換。 因?yàn)?code>(8)比它的父節(jié)點(diǎn)((7))大，我們需要調(diào)用shiftUp()。

用數(shù)組創(chuàng)建堆

將數(shù)組轉(zhuǎn)換為堆可以很方便。 只是對(duì)數(shù)組元素進(jìn)行洗牌，直到滿足堆屬性。

在代碼中它看起來(lái)像這樣：

  private mutating func buildHeap(fromArray array: [T]) {
    for value in array {
      insert(value)
    }
  }

我們只要為數(shù)組中的每個(gè)值調(diào)用insert()。 簡(jiǎn)單但不是很高效。 這總共需要O(n log n)時(shí)間，因?yàn)橛?strong>n個(gè)元素，每個(gè)插入需要log n時(shí)間。

如果你沒(méi)有跳過(guò)前面數(shù)學(xué)部分，你已經(jīng)看到，對(duì)于任何堆，數(shù)組索引n / 2到n-1的元素都是樹的葉節(jié)點(diǎn)。 我們可以簡(jiǎn)單地跳過(guò)那些葉子。 我們只需要處理其他節(jié)點(diǎn)，因?yàn)樗鼈兪怯幸粋€(gè)或多個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)，因此可能是錯(cuò)誤的順序。

代碼:

  private mutating func buildHeap(fromArray array: [T]) {
    elements = array
    for i in stride(from: (nodes.count/2-1), through: 0, by: -1) {
      shiftDown(index: i, heapSize: elements.count)
    }
  }

這里，elements是堆自己的數(shù)組。 我們從第一個(gè)非葉節(jié)點(diǎn)開始向后遍歷這個(gè)數(shù)組，并調(diào)用shiftDown()。 這個(gè)簡(jiǎn)單的循環(huán)以正確的順序放置這些節(jié)點(diǎn)以及我們跳過(guò)的葉節(jié)點(diǎn)。 這被稱為Floyd算法，只需要O(n)時(shí)間。 ??

搜索堆

堆不能用于快速搜索，但如果要使用removeAtIndex()刪除任意元素或使用replace()更改元素的值，則需要獲取該元素的索引。搜索堆速度很慢。

在二叉搜索樹中，根據(jù)節(jié)點(diǎn)的順序，可以保證快速搜索。 由于堆以不同方式對(duì)其節(jié)點(diǎn)進(jìn)行排序，因此二叉搜索不起作用，您需要檢查樹中的每個(gè)節(jié)點(diǎn)。

再給出上面堆示例：

如果我們想要搜索節(jié)點(diǎn)(1)的索引，我們可以通過(guò)線性搜索分步搜索數(shù)組[10, 7, 2, 5, 1]。

即使堆屬性沒(méi)有考慮到搜索，我們?nèi)匀豢梢岳盟?我們知道在max-heap中父節(jié)點(diǎn)總是比它的子節(jié)點(diǎn)大，所以如果父節(jié)點(diǎn)已經(jīng)小于我們要查找的值，我們可以忽略那些子節(jié)點(diǎn)(及其子節(jié)點(diǎn)等等）。

假設(shè)我們想要查看堆是否包含值8(沒(méi)有包含)。 我們從根(10)開始。 這不是我們想要的，所以我們遞歸地看看它的左右子節(jié)點(diǎn)。 左邊的孩子是(7)。 這也不是我們想要的，但由于這是一個(gè)max-heap，我們知道查看(7)的子節(jié)點(diǎn)是沒(méi)有意義的，它們總是小于7，因此左側(cè)不會(huì)找到8。 同樣，對(duì)于右節(jié)點(diǎn)，(2)，也找不到。

盡管有一點(diǎn)優(yōu)化，搜索仍然是O(n)操作。

注意： 有一種方法可以通過(guò)保留一個(gè)將節(jié)點(diǎn)值映射到索引的附加字典來(lái)將查找轉(zhuǎn)換為O(1)操作。 如果你經(jīng)常需要調(diào)用replace()來(lái)改變構(gòu)建在堆上的優(yōu)先隊(duì)列中對(duì)象的“優(yōu)先級(jí)”，這可能是值得做的。

代碼

有關(guān)用Swift代碼實(shí)現(xiàn)，請(qǐng)參見(jiàn)Heap.swift。 大多數(shù)代碼都很簡(jiǎn)單。 唯一棘手的是shiftUp()和shiftDown()。

您已經(jīng)知道有兩種類型的堆：max-heap和min-heap。 它們之間的唯一區(qū)別在于它們?nèi)绾螌?duì)節(jié)點(diǎn)進(jìn)行排序：首先是最大值或最小值。

不是創(chuàng)建兩個(gè)不同的版本，MaxHeap和MinHeap，而只有一個(gè)Heap對(duì)象，它需要一個(gè)isOrderedBefore閉包。 此閉包包含確定兩個(gè)值的順序的邏輯。 你之前可能已經(jīng)看過(guò)了，因?yàn)樗彩荢wift的sort()的工作原理。

要?jiǎng)?chuàng)建一個(gè)max-heap整數(shù)堆：

var maxHeap = Heap<Int>(sort: >)

要?jiǎng)?chuàng)建一個(gè)min-heap整數(shù)堆：

var minHeap = Heap<Int>(sort: <)

I just wanted to point this out, because where most heap implementations use the < and > operators to compare values, this one uses the isOrderedBefore() closure.
我只想指出這一點(diǎn)，因?yàn)榇蠖鄶?shù)堆實(shí)現(xiàn)使用<和>運(yùn)算符來(lái)比較值，這個(gè)使用isOrderedBefore()閉包。

擴(kuò)展閱讀

Heap的維基百科

作者：Kevin Randrup， Matthijs Hollemans
翻譯：Andy Ron
校對(duì)：Andy Ron