堆就是用數(shù)組實(shí)現(xiàn)的二叉樹裕寨，所以它沒有使用父指針或者子指針竹习。堆根據(jù)“堆屬性”來排序伴箩，“堆屬性”決定了樹中節(jié)點(diǎn)的位置孵班。
堆的常用方法：
- 構(gòu)建優(yōu)先隊(duì)列
- 支持堆排序
- 快速找出一個集合中的最小值（或者最大值）
- 在朋友面前裝逼
堆屬性
堆分為兩種：最大堆和最小堆赠潦，兩者的差別在于節(jié)點(diǎn)的排序方式叫胖。
在最大堆中，父節(jié)點(diǎn)的值比每一個子節(jié)點(diǎn)的值都要大她奥。在最小堆中瓮增，父節(jié)點(diǎn)的值比每一個子節(jié)點(diǎn)的值都要小。這就是所謂的“堆屬性”哩俭，并且這個屬性對堆中的每一個節(jié)點(diǎn)都成立绷跑。
例子：
這是一個最大堆，凡资，因?yàn)槊恳粋€父節(jié)點(diǎn)的值都比其子節(jié)點(diǎn)要大砸捏。10 比 7 和 2 都大。7 比 5 和 1都大隙赁。
根據(jù)這一屬性垦藏，那么最大堆總是將其中的最大值存放在樹的根節(jié)點(diǎn)。而對于最小堆伞访，根節(jié)點(diǎn)中的元素總是樹中的最小值膝藕。堆屬性非常有用，因?yàn)槎殉３１划?dāng)做優(yōu)先隊(duì)列使用咐扭，因?yàn)榭梢钥焖俚卦L問到“最重要”的元素。
注意：堆的根節(jié)點(diǎn)中存放的是最大或者最小元素，但是其他節(jié)點(diǎn)的排序順序是未知的蝗肪。例如袜爪，在一個最大堆中，最大的那一個元素總是位于 index 0 的位置薛闪，但是最小的元素則未必是最后一個元素辛馆。--唯一能夠保證的是最小的元素是一個葉節(jié)點(diǎn)，但是不確定是哪一個豁延。
堆和普通樹的區(qū)別
堆并不能取代二叉搜索樹昙篙，它們之間有相似之處也有一些不同。我們來看一下兩者的主要差別：
節(jié)點(diǎn)的順序诱咏。在二叉搜索樹中苔可，左子節(jié)點(diǎn)必須比父節(jié)點(diǎn)小，右子節(jié)點(diǎn)必須必比父節(jié)點(diǎn)大袋狞。但是在堆中并非如此焚辅。在最大堆中兩個子節(jié)點(diǎn)都必須比父節(jié)點(diǎn)小，而在最小堆中苟鸯，它們都必須比父節(jié)點(diǎn)大同蜻。
內(nèi)存占用。普通樹占用的內(nèi)存空間比它們存儲的數(shù)據(jù)要多早处。你必須為節(jié)點(diǎn)對象以及左/右子節(jié)點(diǎn)指針分配內(nèi)存湾蔓。堆僅僅使用一個數(shù)據(jù)來存儲數(shù)組，且不使用指針砌梆。
平衡默责。二叉搜索樹必須是“平衡”的情況下，其大部分操作的復(fù)雜度才能達(dá)到O(log n)么库。你可以按任意順序位置插入/刪除數(shù)據(jù)傻丝，或者使用 AVL 樹或者紅黑樹，但是在堆中實(shí)際上不需要整棵樹都是有序的诉儒。我們只需要滿足堆屬性即可葡缰，所以在堆中平衡不是問題。因?yàn)槎阎袛?shù)據(jù)的組織方式可以保證O(log n) 的性能忱反。
搜索泛释。在二叉樹中搜索會很快，但是在堆中搜索會很慢温算。在堆中搜索不是第一優(yōu)先級怜校，因?yàn)槭褂枚训哪康氖菍⒆畲螅ɑ蛘咦钚。┑墓?jié)點(diǎn)放在最前面注竿，從而快速的進(jìn)行相關(guān)插入茄茁、刪除操作魂贬。
來自數(shù)組的樹
用數(shù)組來實(shí)現(xiàn)樹相關(guān)的數(shù)據(jù)結(jié)構(gòu)也許看起來有點(diǎn)古怪，但是它在時間和空間上都是很高效的裙顽。
我們準(zhǔn)備將上面例子中的樹這樣存儲：
[ 10, 7, 2, 5, 1 ]
就這么多付燥！我們除了一個簡單的數(shù)組以外，不需要任何額外的空間愈犹。
如果我們不允許使用指針键科，那么我們怎么知道哪一個節(jié)點(diǎn)是父節(jié)點(diǎn)，哪一個節(jié)點(diǎn)是它的子節(jié)點(diǎn)呢漩怎？問得好勋颖！節(jié)點(diǎn)在數(shù)組中的位置index 和它的父節(jié)點(diǎn)以及子節(jié)點(diǎn)的索引之間有一個映射關(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饭玲。左右節(jié)點(diǎn)總是處于相鄰的位置。
我們將寫公式放到前面的例子中驗(yàn)證一下怪得。
| Node | Array index (i) |
Parent index | Left child | Right child |
|---|---|---|---|---|
| 10 | 0 | -1 | 1 | 2 |
| 7 | 1 | 0 | 3 | 4 |
| 2 | 2 | 0 | 5 | 6 |
| 5 | 3 | 1 | 7 | 8 |
| 1 | 4 | 1 | 9 | 10 |
注意：根節(jié)點(diǎn)
(10)沒有父節(jié)點(diǎn)咱枉，因?yàn)?-1不是一個有效的數(shù)組索引。同樣徒恋，節(jié)點(diǎn)(2)蚕断，(5)和(1)沒有子節(jié)點(diǎn)，因?yàn)檫@些索引已經(jīng)超過了數(shù)組的大小入挣，所以我們在使用這些索引值的時候需要保證是有效的索引值亿乳。
復(fù)習(xí)一下，在最大堆中径筏，父節(jié)點(diǎn)的值總是要大于（或者等于）其子節(jié)點(diǎn)的值葛假。這意味下面的公式對數(shù)組中任意一個索引 i都成立：
array[parent(i)] >= array[i]
可以用上面的例子來驗(yàn)證一下這個堆屬性。
如你所見滋恬，這些公式允許我們不使用指針就可以找到任何一個節(jié)點(diǎn)的父節(jié)點(diǎn)或者子節(jié)點(diǎn)聊训。事情比簡單的去掉指針要復(fù)雜，但這就是交易：我們節(jié)約了空間恢氯，但是要進(jìn)行更多計算带斑。幸好這些計算很快并且只需要O(1)的時間。
理解數(shù)組索引和節(jié)點(diǎn)位置之間的關(guān)系非常重要勋拟。這里有一個更大的堆勋磕，它有15個節(jié)點(diǎn)被分成了4層：
圖片中的數(shù)字不是節(jié)點(diǎn)的值挂滓，而是存儲這個節(jié)點(diǎn)的數(shù)組索引啸胧！這里是數(shù)組索引和樹的層級之間的關(guān)系：
由上圖可以看到幔虏，數(shù)組中父節(jié)點(diǎn)總是在子節(jié)點(diǎn)的前面。
注意這個方案與一些限制贝椿。你可以在普通二叉樹中按照下面的方式組織數(shù)據(jù)所计，但是在堆中不可以：
在堆中，在當(dāng)前層級所有的節(jié)點(diǎn)都已經(jīng)填滿之前不允許開是下一層的填充团秽，所以堆總是有這樣的形狀：
注意：你可以使用普通樹來模擬堆，但是那對空間是極大的浪費(fèi)叭首。
小測驗(yàn)习勤，假設(shè)我們有這樣一個數(shù)組：
[ 10, 14, 25, 33, 81, 82, 99 ]
這是一個有效的堆嗎？答案是 yes 焙格！一個從低到高有序排列的數(shù)組是以有效的最小堆图毕，我們可以將這個堆畫出來：
堆屬性適用于每一個節(jié)點(diǎn)，因?yàn)楦腹?jié)點(diǎn)總是比它的字節(jié)點(diǎn)小眷唉。（你也可以驗(yàn)證一下：一個從高到低有序排列的數(shù)組是一個有效的最大堆）
注意：并不是每一個最小堆都是一個有序數(shù)組予颤！要將堆轉(zhuǎn)換成有序數(shù)組，需要使用堆排序冬阳。
更多數(shù)學(xué)公式
如果你好奇蛤虐，這里有更多的公式描述了堆的一些確定屬性。你不需要知道這些肝陪，但它們有時會派上用場驳庭。 可以直接跳過此部分！
樹的高度是指從樹的根節(jié)點(diǎn)到最低的葉節(jié)點(diǎn)所需要的步數(shù)氯窍，或者更正式的定義：高度是指節(jié)點(diǎn)之間的邊的最大值饲常。一個高度為 h 的堆有 h+1 層。
下面這個對的高度是3狼讨，所以它有4層：
如果一個堆有 n 個節(jié)點(diǎn)贝淤，那么它的高度是 h = floor(log2(n))。這是因?yàn)槲覀兛偸且獙⑦@一層完全填滿以后才會填充新的一層政供。上面的例子有 15 個節(jié)點(diǎn)播聪，所以它的高度是 floor(log2(15)) = floor(3.91) = 3。
如果最下面的一層已經(jīng)填滿鲫骗，那么那一層包含 2^h 個節(jié)點(diǎn)执泰。樹中這一層以上所有的節(jié)點(diǎn)數(shù)目為 2^h - 1术吝。同樣是上面這個例子，最下面的一層有8個節(jié)點(diǎn)学密，實(shí)際上就是 2^3 = 8腻暮。前面的三層一共包含7的節(jié)點(diǎn)哭靖，即：2^3 - 1 = 8 - 1 = 7试幽。
所以整個堆中的節(jié)點(diǎn)數(shù)目為：* 2^(h+1) - 1*铺坞。上面的例子中济榨，2^4 - 1 = 16 - 1 = 15
葉節(jié)點(diǎn)總是位于數(shù)組的 floor(n/2) 和 n-1 之間。
可以用堆做什么绘梦？
有兩個原始操作用于保證插入或刪除節(jié)點(diǎn)以后堆是一個有效的最大堆或者最小堆：
-
shiftUp(): 如果一個節(jié)點(diǎn)比它的父節(jié)點(diǎn)大（最大堆）或者卸鄢稀（最小堆）凝颇，那么需要將它同父節(jié)點(diǎn)交換位置拧略。這樣是這個節(jié)點(diǎn)在數(shù)組的位置上升垫蛆。 -
shiftDown(): 如果一個節(jié)點(diǎn)比它的子節(jié)點(diǎn)写ㄎ蕖（最大堆）或者大（最小堆）懦趋，那么需要將它向下移動仅叫。這個操作也稱作“堆化（heapify）”糙捺。
shiftUp 或者 shiftDown 是一個遞歸的過程，所以它的時間復(fù)雜度是 O(log n)逃沿。
基于這兩個原始操作還有一些其他的操作：
-
insert(value): 在堆的尾部添加一個新的元素凯亮，然后使用shiftUp來修復(fù)對假消。 -
remove(): 移除并返回最大值（最大堆）或者最小值（最小堆）。為了將這個節(jié)點(diǎn)刪除后的空位填補(bǔ)上臼予，需要將最后一個元素移到根節(jié)點(diǎn)的位置粘拾，然后使用shiftDown方法來修復(fù)堆。 -
removeAtIndex(index): 和remove()一樣追驴，差別在于可以移除堆中任意節(jié)點(diǎn)殿雪，而不僅僅是根節(jié)點(diǎn)糯崎。當(dāng)它與子節(jié)點(diǎn)比較位置不時無序時使用shiftDown()，如果與父節(jié)點(diǎn)比較發(fā)現(xiàn)無序則使用shiftUp()年栓。 -
replace(index, value)：將一個更小的值（最小堆）或者更大的值（最大堆）賦值給一個節(jié)點(diǎn)。由于這個操作破壞了堆屬性惰瓜，所以需要使用shiftUp()來修復(fù)堆屬性崎坊。
上面所有的操作的時間復(fù)雜度都是 O(log n)奈揍，因?yàn)?shiftUp 和 shiftDown 都很費(fèi)時男翰。還有少數(shù)一些操作需要更多的時間：
-
search(value):堆不是為快速搜索而建立的昆箕，但是replace()和removeAtIndex()操作需要找到節(jié)點(diǎn)在數(shù)組中的index鹏倘，所以你需要先找到這個index第股。時間復(fù)雜度：O(n)夕吻。 -
buildHeap(array):通過反復(fù)調(diào)用insert()方法將一個（無序）數(shù)組轉(zhuǎn)換成一個堆涉馅。如果你足夠聰明稚矿，你可以在 O(n) 時間內(nèi)完成晤揣。 - 堆排序：由于堆就是一個數(shù)組，我們可以使用它獨(dú)特的屬性將數(shù)組從低到高排序钠四。時間復(fù)雜度：O(n lg n)缀去。
堆還有一個 peek() 方法，不用刪除節(jié)點(diǎn)就返回最大值（最大堆）或者最小值（最小堆）咏雌。時間復(fù)雜度 O(1) 处嫌。
注意：到目前為止，堆的常用操作還是使用
insert()插入一個新的元素凝赛，和通過remove()移除最大或者最小值墓猎。兩者的時間復(fù)雜度都是O(log n)毙沾。其其他的操作是用于支持更高級的應(yīng)用左胞，比如說建立一個優(yōu)先隊(duì)列。
插入
我們通過一個插入例子來看看插入操作的細(xì)節(jié)躺枕。我們將數(shù)字 16 插入到這個堆中：
堆的數(shù)組是： [ 10, 7, 2, 5, 1 ]罢猪。
第一股是將新的元素插入到數(shù)組的尾部膳帕。數(shù)組變成：
[ 10, 7, 2, 5, 1, 16 ]
相應(yīng)的樹變成了：
16 被添加最后一行的第一個空位。
不行的是恬砂，現(xiàn)在堆屬性不滿足蓬痒，因?yàn)?2 在 16 的上面狱掂，我們需要將大的數(shù)字在上面（這是一個最大堆）
為了恢復(fù)堆屬性趋惨，我們需要交換 16 和 2器虾。
現(xiàn)在還沒有完成，因?yàn)?10 也比 16 小葛圃。我們繼續(xù)交換我們的插入元素和它的父節(jié)點(diǎn)库正，直到它的父節(jié)點(diǎn)比它大或者我們到達(dá)樹的頂部。這就是所謂的 shift-up属瓣，每一次插入操作后都需要進(jìn)行抡蛙。它將一個太大或者太小的數(shù)字“浮起”到樹的頂部惋耙。
最后我們得到的堆：
現(xiàn)在每一個父節(jié)點(diǎn)都比它的子節(jié)點(diǎn)大。
刪除根節(jié)點(diǎn)
我們將這個樹中的 (10) 刪除：
現(xiàn)在頂部有一個空的節(jié)點(diǎn)婿屹，怎么處理灭美？
當(dāng)插入節(jié)點(diǎn)的時候，我們將新的值返給數(shù)組的尾部“豪現(xiàn)在我們來做相反的事情：我們?nèi)〕鰯?shù)組中的最后一個元素届腐，將它放到樹的頂部，然后再修復(fù)堆屬性蜂奸。
現(xiàn)在來看怎么 shift-down (1)犁苏。為了保持最大堆的堆屬性，我們需要樹的頂部是最大的數(shù)據(jù)±┧現(xiàn)在有兩個數(shù)字可用于交換 7 和 2围详。我們選擇這兩者中的較大者稱為最大值放在樹的頂部，所以交換 7 和 1漠嵌，現(xiàn)在樹變成了：
繼續(xù)堆化直到該節(jié)點(diǎn)沒有任何子節(jié)點(diǎn)或者它比兩個子節(jié)點(diǎn)都要大為止植阴。對于我們的堆喷鸽，我們只需要再有一次交換就恢復(fù)了堆屬性：
刪除任意節(jié)點(diǎn)
絕大多數(shù)時候你需要刪除的是堆的根節(jié)點(diǎn)，因?yàn)檫@就是堆的設(shè)計用途翻诉。
但是，刪除任意節(jié)點(diǎn)也很有用。這是 remove() 的通用版本岂贩，它可能會使用到 shiftDown 和 shiftUp。
我們還是用前面的例子颈渊，刪除 (7):
[圖片上傳失敗...(image-d46ac4-1534077058042)]
對應(yīng)的數(shù)組是
[ 10, 7, 2, 5, 1 ]
你知道，移除一個元素會破壞最大堆或者最小堆屬性。我們需要將刪除的元素和最后一個元素交換：
[ 10, 1, 2, 5, 7 ]
最后一個元素就是我們需要返回的元素驶拱；然后調(diào)用 removeLast() 來將它刪除税迷。 (1) 比它的子節(jié)點(diǎn)小喝检，所以需要 shiftDown() 來修復(fù)。
然而外永，shift down 不是我們要處理的唯一情況阅签。也有可能我們需要 shift up养交∶蹈洌考慮一下從下面的堆中刪除 (5) 會發(fā)生什么：
現(xiàn)在 (5) 和 (8) 交換了孵运。因?yàn)?(8) 比它的父節(jié)點(diǎn)大等孵，我們需要 shiftUp()返弹。
