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

堆的常見(jiàn)用途：

• 建立優(yōu)先級(jí)隊(duì)列。

• 支持堆排序。

• 快速計(jì)算集合的最小(或最大)元素。

堆屬性

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

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

一個(gè)例子：

image.png

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

由于具有此堆屬性，因此，max-heap始終將其最大的項(xiàng)存儲(chǔ)在樹的根目錄中。對(duì)于最小堆，根始終是樹中最小的項(xiàng)。堆屬性很有用，因?yàn)槎呀?jīng)常被用作優(yōu)先級(jí)隊(duì)列來(lái)快速訪問(wèn)“最重要”元素。

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

堆與常規(guī)樹相比如何？

堆不能代替二叉搜索樹，它們之間有相似之處和不同之處。主要區(qū)別如下：

節(jié)點(diǎn)順序。在二叉搜索樹(BST)中，左子級(jí)必須小于其父級(jí)，而右子級(jí)必須更大。對(duì)于堆來(lái)說(shuō)不是這樣。在最大堆中，兩個(gè)子項(xiàng)都必須小于父項(xiàng)，而在最小堆中，兩個(gè)子項(xiàng)都必須更大。

記憶。傳統(tǒng)的樹占用的內(nèi)存不僅僅是它們存儲(chǔ)的數(shù)據(jù)。您需要為節(jié)點(diǎn)對(duì)象和指向左/右子節(jié)點(diǎn)的指針?lè)峙淦渌鎯?chǔ)。堆僅使用普通數(shù)組進(jìn)行存儲(chǔ)，并且不使用指針。

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

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

數(shù)組內(nèi)的樹

數(shù)組似乎是實(shí)現(xiàn)樹狀結(jié)構(gòu)的一種奇怪方法，但它在時(shí)間和空間上都是有效的。

這就是上面示例中存儲(chǔ)樹的方式：

[ 10, 7, 2, 5, 1 ]

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

因此，如果不允許使用任何指針，我們?nèi)绾沃滥男┕?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

請(qǐng)注意，這right(i)很簡(jiǎn)單left(i) + 1。左節(jié)點(diǎn)和右節(jié)點(diǎn)始終彼此相鄰存儲(chǔ)。

讓我們?cè)谑纠惺褂眠@些公式。填寫數(shù)組索引，我們應(yīng)該獲得父節(jié)點(diǎn)和子節(jié)點(diǎn)在數(shù)組中的位置：

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

注意：根節(jié)點(diǎn)(10)沒(méi)有父節(jié)點(diǎn)，因?yàn)?code>-1它不是有效的數(shù)組索引。同樣，node (2)，(5)和(1)沒(méi)有子項(xiàng)，因?yàn)檫@些索引大于數(shù)組的大小，因此在使用它們之前，我們始終必須確保計(jì)算出的索引實(shí)際上是有效的。

回想一下，在最大堆中，父級(jí)的值始終大于(或等于)其子級(jí)的值。這意味著所有數(shù)組索引必須滿足以下條件i：

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

驗(yàn)證此堆屬性對(duì)于示例堆中的數(shù)組是否成立。

如您所見(jiàn)，這些方程式使我們無(wú)需指針即可查找任何節(jié)點(diǎn)的父級(jí)或子級(jí)索引。這不僅只是取消引用指針，還很復(fù)雜，但這是一個(gè)折衷方案：我們節(jié)省了內(nèi)存空間，但需要額外的計(jì)算。幸運(yùn)的是，計(jì)算速度很快，只需要O(1)時(shí)間。

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

image.png

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

image.png

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

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

image.png

除非當(dāng)前最低級(jí)別已滿，否則您無(wú)法啟動(dòng)新級(jí)別，因此堆始終具有以下形狀：

image.png

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

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

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

這是有效的堆嗎？答案是肯定的！從低到高排序的數(shù)組是有效的最小堆。我們可以如下繪制該堆：

image.png

堆屬性對(duì)于每個(gè)節(jié)點(diǎn)均有效，因?yàn)楦腹?jié)點(diǎn)始終小于其子節(jié)點(diǎn)。(親自驗(yàn)證從高到低排序的數(shù)組始終是有效的最大堆。)

注意：但是，并非每一個(gè)min-heap都一定是一個(gè)有序數(shù)組！它僅以一種方式起作用。要將堆轉(zhuǎn)換回已排序的數(shù)組，需要使用堆排序。

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

如果您感到好奇，這里還有一些描述堆的某些屬性的公式。您不需要內(nèi)心地了解這些內(nèi)容，但是有時(shí)它們會(huì)派上用場(chǎng)。隨時(shí)跳過(guò)此部分！

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

該堆的高度為3，因此具有4個(gè)級(jí)別：

image.png

具有n個(gè)節(jié)點(diǎn)的堆的高度為h = floor(log2(n))。這是因?yàn)樵谔砑有录?jí)別之前，我們總是會(huì)完全填滿最低級(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)。填寫示例中的數(shù)字：最低級(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。

有至多ceil(n/2^(h+1))高度的節(jié)點(diǎn)在一個(gè) n-element heap。

葉子節(jié)點(diǎn)始終位于數(shù)組索引floor(n / 2)到n-1處。我們將利用這一事實(shí)從陣列中快速構(gòu)建堆。如果您不相信該示例，請(qǐng)對(duì)其進(jìn)行驗(yàn)證。;-)

僅有的一些數(shù)學(xué)事實(shí)可以幫助您改善生活。

你能用堆做什么？

在插入或刪除元素之后，有兩項(xiàng)基本操作可確保堆是有效的max-heap或min-heap：

• shiftUp()：如果元素大于其父元素(最大堆)或小于其父元素(最小堆)，則需要與父元素交換。這使它向上移動(dòng)到樹上。

• shiftDown()。如果元素比其子元素小(最大堆)或更大(最小堆)，則需要向下移動(dòng)樹。此操作也稱為“堆化”。

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

以下是在原始操作上構(gòu)建的其他操作：

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

• remove()：刪除并返回最大值(最大堆)或最小值(最小堆)。要通過(guò)刪除元素來(lái)填補(bǔ)剩余的空缺，將最后一個(gè)元素移到根位置，然后shiftDown()修復(fù)堆。(有時(shí)稱為“提取最小值”或“提取最大值”。)

• removeAtIndex(index)：就像remove()例外一樣，它允許您從堆中刪除任何項(xiàng)，而不僅僅是根。shiftDown()如果新元素的子元素不正常，則調(diào)用，如果元素shiftUp()的父元素不正常，則調(diào)用。

• replace(index, value)：為節(jié)點(diǎn)分配較小(最小堆)或較大(最大堆)的值。因?yàn)檫@會(huì)使堆屬性無(wú)效，所以它用于shiftUp()修補(bǔ)事物。(也稱為“減少鍵”和“增加鍵”。)

上述所有操作都需要時(shí)間O(log n)，因?yàn)樯弦苹蛳乱频馁M(fèi)用很高。還有一些操作需要更多時(shí)間：

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

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

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

堆還具有一個(gè)peek()返回最大(max-heap)或最小(min-heap)元素的函數(shù)，而無(wú)需將其從堆中刪除。時(shí)間：O(1)。

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

插入堆

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

image.png

此堆的數(shù)組是[ 10, 7, 2, 5, 1 ]。

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

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

這對(duì)應(yīng)于以下樹：

image.png

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

不幸的是，由于(2)位于上面(16)，不再滿足heap屬性，因此我們希望較高的數(shù)字高于較低的數(shù)字。(這是一個(gè)最大堆。)

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

image.png

我們尚未完成，因?yàn)?code>(10)還小于(16)。我們一直將插入的值與其父級(jí)交換，直到父級(jí)更大或到達(dá)樹頂為止。這稱為上移或篩分，并在每次插入后完成。它使數(shù)字太大或太小都會(huì)“浮起”樹。

最后，我們得到：

image.png

現(xiàn)在，每個(gè)父母都比孩子更大。

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

移除根

讓我們(10)從這棵樹中刪除：

image.png

頂部的空白處會(huì)發(fā)生什么？

image.png

插入時(shí)，我們將新值放在數(shù)組的末尾。在這里，我們做相反的事情：我們拿走我們擁有的最后一個(gè)對(duì)象，將其粘貼在樹的頂部，然后恢復(fù)heap屬性。

image.png

讓我們看一下如何調(diào)低檔位 (1)。為了維護(hù)此max-heap的heap屬性，我們希望獲得最大數(shù)量的top。我們有兩個(gè)候選人可以與(7)和交換名額(2)。我們?cè)谶@三個(gè)節(jié)點(diǎn)之間選擇最高的數(shù)字。也就是(7)，因此交換(1)并(7)給我們下面的樹。

image.png

繼續(xù)向下移動(dòng)，直到該節(jié)點(diǎn)沒(méi)有任何子節(jié)點(diǎn)或該節(jié)點(diǎn)大于其兩個(gè)子節(jié)點(diǎn)為止。對(duì)于我們的堆，我們只需要再進(jìn)行一次交換即可恢復(fù)堆屬性：

image.png

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

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

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

在絕大多數(shù)情況下，您將在堆的根部刪除對(duì)象，因?yàn)檫@是為堆設(shè)計(jì)的。

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

讓我們?cè)俅我允纠龢錇槔?，并刪除(7)：

image.png

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

[ 10, 7, 2, 5, 1 ]

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

[ 10, 1, 2, 5, 7 ]

最后一個(gè)元素是我們將返回的元素；我們將調(diào)用removeLast()將其從堆中刪除。在(1)現(xiàn)在是亂序，因?yàn)樗绕渥有。?code>(5)但坐在樹高。我們致電shiftDown()維修。

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

image.png

現(xiàn)在(5)與交換(8)。由于(8)大于其父項(xiàng)，因此我們需要致電shiftUp()。

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

將數(shù)組轉(zhuǎn)換為堆可能很方便。這只是隨機(jī)排列數(shù)組元素，直到滿足heap屬性為止。

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

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

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

如果您不對(duì)數(shù)學(xué)部分有所了解，您會(huì)發(fā)現(xiàn)對(duì)于任何堆，數(shù)組索引為n / 2到n-1的元素都是樹的葉子。我們可以簡(jiǎn)單地跳過(guò)那些葉子。我們只需要處理其他節(jié)點(diǎn)，因?yàn)樗鼈兪怯幸粋€(gè)或多個(gè)孩子的父母，因此順序可能不正確。

在代碼中：

  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)開始向后遍歷此數(shù)組，然后調(diào)用shiftDown()。這個(gè)簡(jiǎn)單的循環(huán)將這些節(jié)點(diǎn)以及我們跳過(guò)的葉子按正確的順序放置。這就是所謂的Floyd算法，只需要O(n)時(shí)間。贏得！

搜索堆

堆不是為了快速搜索而創(chuàng)建的，但是如果要使用刪除任意元素removeAtIndex()或使用來(lái)更改元素的值replace()，則需要獲取該元素的索引。搜索是執(zhí)行此操作的一種方法，但是速度很慢。

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

讓我們?cè)俅我允纠褳槔?/p>

image.png

如果要搜索node的索引(1)，可以通過(guò)[ 10, 7, 2, 5, 1 ]線性搜索逐步遍歷數(shù)組。

即使沒(méi)有考慮到堆屬性的構(gòu)想，我們?nèi)匀豢梢岳盟Ｎ覀冎?，在最大堆中，父?jié)點(diǎn)始終大于其子節(jié)點(diǎn)，因此，如果父節(jié)點(diǎn)已經(jīng)小于要尋找的值，則可以忽略那些子節(jié)點(diǎn)(及其子節(jié)點(diǎn)，依此類推...)。

假設(shè)我們要查看堆是否包含值8(不包含)。我們從根本開始(10)。這不是我們想要的，所以我們遞歸地查看它的左子對(duì)象和右子對(duì)象。左孩子是(7)。這也不是我們想要的，但是由于這是一個(gè)最大堆，我們知道查看的子項(xiàng)是沒(méi)有意義的(7)。它們總是小于7并且因此永遠(yuǎn)不等于8; 同樣，對(duì)于合適的孩子，(2)。

盡管有很小的優(yōu)化，搜索仍然是O(n)操作。

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

原文鏈接：堆