二叉堆
這個(gè)二叉堆和先進(jìn)后出的那個(gè)堆不是一個(gè)。
而且這個(gè)二叉堆從下標(biāo)1開始存儲(chǔ)元素。
這里的二叉堆是個(gè)數(shù)組删掀，也可以看作是一個(gè)完全二叉樹，除了最底層外导街，這顆二叉樹是完全充滿的披泪。
堆數(shù)據(jù)結(jié)構(gòu)：利用數(shù)組模擬了一個(gè)完全二叉樹。(這里的堆不是那個(gè)先進(jìn)后出的數(shù)據(jù)結(jié)構(gòu))
將樹的根節(jié)點(diǎn)存放在數(shù)組的[1]位置搬瑰。第二層的連個(gè)存放在[2]`[3]`,第三層存放在`[4]`[7]……
所以可以得到這樣的規(guī)律：
數(shù)組中每個(gè)元素（假設(shè)在數(shù)組中的下標(biāo)為k）在二叉樹中的左節(jié)點(diǎn)存放在數(shù)組的[2k]中款票，而右節(jié)點(diǎn)存放在[2k+1]中控硼。
通過數(shù)組來模擬一個(gè) 完全二叉樹，從而實(shí)現(xiàn)排序的算法：堆排序
堆排序
二叉堆分為兩種：最大二叉堆和最小二叉堆:
- 最大二叉堆（下面都以此為例）
每個(gè)節(jié)點(diǎn)[k]的值都比其左節(jié)點(diǎn)[2k]和右節(jié)點(diǎn)[2k+1]要大艾少。但是卡乾，左右這兩個(gè)節(jié)點(diǎn)之間的大小是不確定的，可以隨意 - 最小二叉堆
反之缚够，每個(gè)節(jié)點(diǎn)都小于其左右節(jié)點(diǎn)幔妨。
性質(zhì)
為了維護(hù)這種性質(zhì)，所以需要一個(gè)函數(shù)去對(duì)比相對(duì)根節(jié)點(diǎn)和起左右節(jié)點(diǎn)的大小谍椅，然后選出一個(gè)最大的放在相對(duì)根節(jié)點(diǎn)的位置误堡。然后如果相對(duì)根節(jié)點(diǎn)被換到左或者右節(jié)點(diǎn)，這時(shí)候又要去檢測(cè)換完以后的一個(gè)小樹叉的性質(zhì)毯辅。所以這需要一個(gè)遞歸或者迭代再去檢測(cè)新的相對(duì)根節(jié)點(diǎn)和其左右子節(jié)點(diǎn)（也就是之前的根節(jié)點(diǎn)被換到的位置）埂伦。
在對(duì)比相對(duì)根節(jié)點(diǎn)和其左右子節(jié)點(diǎn)之前，需要先判斷這個(gè)相對(duì)根節(jié)點(diǎn)是否存在左右子節(jié)點(diǎn)思恐，也就是左右節(jié)點(diǎn)在數(shù)組中的下標(biāo)是否越界沾谜。
在最大二叉堆中，維護(hù)這種性質(zhì)是使小元素下沉的過程（大元素只能上浮一個(gè)位置）胀莹。
建堆
為了將一個(gè)數(shù)組建成一個(gè)二叉堆基跑，需要事數(shù)組中的元素符合上述性質(zhì)。
所以我么你可以遍歷每一個(gè)元素描焰，這樣她就可以滿足了媳否。
維護(hù)二叉堆性質(zhì)的函數(shù)是讓小元素下沉,而大元素只能上浮一層。所以荆秦，如果采用從頭到尾遍歷的話篱竭，那么大元素也只能上浮一層。
而采用從后向前遍歷的話步绸，在一層中一個(gè)大元素上浮以后掺逼，該函數(shù)遍歷道上一層以后，又會(huì)在該節(jié)點(diǎn)執(zhí)行一次瓤介。這樣一個(gè)大元素可以被一直往上“趕”吕喘。
插入和刪除
如果非要在二叉堆上實(shí)現(xiàn)插入和刪除的話：
- 刪除
刪除任意一個(gè)點(diǎn)，后面的數(shù)據(jù)先前進(jìn)一位刑桑，會(huì)造成后面大量的樹叉的性質(zhì)改變氯质。
所以，采用另一種方式祠斧，把要?jiǎng)h除的元素（下標(biāo)為k）和最后一個(gè)元素交換闻察，然山刪除數(shù)組的最后一個(gè)元素。
這時(shí)候只要調(diào)用維護(hù)性質(zhì)的函數(shù)，將k位置的元素下沉就行了蜓陌。
所以可以這個(gè)實(shí)現(xiàn)觅彰，依次將最大的元素刪除或者提出。
- 添加的話（假設(shè)使用的是
vector存儲(chǔ)不是數(shù)組）钮热，那么需要將最后一位（也就是添加的）和第一位交換填抬，然后重新建堆。
優(yōu)先隊(duì)列
如果將二叉堆中排序的元素看作是一種結(jié)構(gòu)體隧期，他有一個(gè)key：也就是被排序的值飒责，還有一個(gè)value：也就是該元素自身所帶有的值。
那么就可以實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列仆潮。
key是權(quán)重宏蛉，也就是要被處理的優(yōu)先級(jí)。而value可以時(shí)要被處理的信息性置。
每次優(yōu)先隊(duì)列（二叉堆）pop出權(quán)重最大的元素拾并，然后被某個(gè)函數(shù)處理。
