二叉堆的解釋
（動(dòng)態(tài)選擇優(yōu)先級(jí)最高的任務(wù)執(zhí)行）
堆止后，又稱(chēng)為優(yōu)先隊(duì)列奈辰。雖然名為優(yōu)先隊(duì)列忙上，但堆并不是隊(duì)列藕漱。堆和隊(duì)列是兩種不同的數(shù)據(jù)結(jié)構(gòu)景醇，堆是樹(shù)態(tài)的臀稚，隊(duì)列是線性的。在隊(duì)列中三痰，我們可以向隊(duì)列添加元素吧寺，取出的時(shí)候是按照進(jìn)入隊(duì)列的先后順序取出元素的，先進(jìn)先出散劫；而在堆中稚机，卻不是按照元素添加的先后順序，而是按照元素的優(yōu)先級(jí)取出元素获搏。
所以二叉堆是為了找出最大或最小而生的赖条，“大”和“小”并不是傳統(tǒng)意義上的小大，而是優(yōu)先級(jí)的高低常熙。二叉堆分為最大堆和最小堆纬乍，最大堆的頂點(diǎn)可以看作是優(yōu)先級(jí)最高的也可以看作是優(yōu)先級(jí)最低的，最小堆也是如此裸卫。
二叉堆是一種完全二叉樹(shù)仿贬，因?yàn)橥耆鏄?shù)的特性普遍使用數(shù)組結(jié)構(gòu)是非常好用的，所以性注定了二叉堆的存儲(chǔ)形式只能是數(shù)組或者動(dòng)態(tài)數(shù)組（長(zhǎng)度可變）墓贿。
二叉堆最主要的操作是兩個(gè)茧泪，siftUp上浮和siftDown下沉，來(lái)保證二叉堆的性質(zhì)：
1.父節(jié)點(diǎn)的鍵值總是優(yōu)先于任何一個(gè)子節(jié)點(diǎn)的鍵值聋袋；
2.左右子樹(shù)都是以一個(gè)二叉堆队伟。
展示最大堆
用數(shù)組存儲(chǔ)二叉堆，堆的頂點(diǎn)下標(biāo)可以從0開(kāi)始也可以從1開(kāi)始舱馅＄峙荩看上面圖中，以self為參照物代嗤，self下標(biāo)的變量為i：
parent(i) = (i - 1) / 2;
leftChild(i) = 2 * i + 1棘钞；
rightChild(i) = leftChild(i) + 1 = 2 * i + 2;
如果是堆頂下標(biāo)從1開(kāi)始：
parent(i) = i / 2;
leftChild = 2 * i;
rightChild = 2 * i + 1;
向堆中添加元素siftUp
二叉堆的節(jié)點(diǎn)添加，是在數(shù)組的最末尾插入新節(jié)點(diǎn)的干毅，然后進(jìn)行自下而上調(diào)整子節(jié)點(diǎn)和父節(jié)點(diǎn)宜猜，不滿足二叉堆性質(zhì)則交換，直到當(dāng)前子樹(shù)滿足二叉堆的性質(zhì)硝逢。如果可以為了減少交換次數(shù)的話姨拥，可以單向復(fù)制绅喉，使得添加的節(jié)點(diǎn)插入到合適的位置。
動(dòng)畫(huà)siftUp
Code：?jiǎn)蜗驈?fù)制
Code：交換法
取出堆中最大的元素siftDown
取出堆中最大的元素其實(shí)是取出根節(jié)點(diǎn)叫乌，這個(gè)下沉的操作很有意思了柴罐。它有兩方面的下沉：一方面是將根節(jié)點(diǎn)下沉到數(shù)組末尾，然后數(shù)組長(zhǎng)度假象性減一下憨奸；另一方面是將交換后的根節(jié)點(diǎn)和左右子樹(shù)的根節(jié)點(diǎn)作比較革屠，不滿足堆性質(zhì)的則交換。
動(dòng)畫(huà)siftDown
Code：siftDown單向復(fù)制
Code：siftDown交換法
構(gòu)建二叉堆
構(gòu)建二叉堆其實(shí)是一個(gè)一個(gè)子樹(shù)的下沉操作排宰，將無(wú)序的完全二叉樹(shù)調(diào)整為二叉堆似芝。所以它必須從滿足高度為2的子樹(shù)根節(jié)點(diǎn)開(kāi)始，即非葉子節(jié)點(diǎn)板甘，然后自底向上對(duì)每一個(gè)子樹(shù)執(zhí)行siftDown操作党瓮，直到完成二叉堆化。
動(dòng)畫(huà)：構(gòu)建二叉堆
Code
喜歡本文的朋友盐类，微信搜索「算法無(wú)遺策」公眾號(hào)寞奸，收看更多精彩的算法動(dòng)畫(huà)文章
