- 相關(guān)推薦
堆的javascript實(shí)現(xiàn)方法
堆的定義
最大（最小）堆是一棵每一個(gè)節(jié)點(diǎn)的鍵值都不小于（大于）其孩子（如果存在）的鍵值的樹(shù)。大頂堆是一棵完全二叉樹(shù)，同時(shí)也是一棵最大樹(shù)。小頂堆是一棵完全完全二叉樹(shù)，同時(shí)也是一棵最小樹(shù)。
另外，記住這兩個(gè)概念，對(duì)寫(xiě)代碼太重要了：
1、父節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系：看定義
2、完全二叉樹(shù)：參考[2]
基本操作
1、Build（構(gòu)建堆）
2、Insert(插入）
3、Delete（刪除：最小或者最大的那個(gè)）
代碼實(shí)現(xiàn)
首先，寫(xiě)代碼前有兩個(gè)非常重要的點(diǎn)：
1、用一個(gè)數(shù)組就可以作為堆的存儲(chǔ)結(jié)構(gòu)，非常簡(jiǎn)單而且易操作；
2、另外同樣因?yàn)槭菙?shù)組作為存儲(chǔ)結(jié)構(gòu)，所以父子節(jié)點(diǎn)之間的關(guān)系就能根據(jù)索引就輕松找到對(duì)方了。
對(duì)于JavaScript以0作為數(shù)組索引開(kāi)始，關(guān)系如下：
nLeftIndex = 2 * (nFatherIndex+1) - 1;nRightIndex = 2* (nFatherIndex+1);
前面提到注意兩個(gè)概念，是有助于理解的：
1、因?yàn)槭菙?shù)組，所以父子節(jié)點(diǎn)的關(guān)系就不需要特殊的結(jié)構(gòu)去維護(hù)了，索引之間通過(guò)計(jì)算就可以得到，省掉了很多麻煩。如果是鏈表結(jié)構(gòu)，就會(huì)復(fù)雜很多；
2、完全二叉樹(shù)的概念可以參考[2]，要求葉子節(jié)點(diǎn)從左往右填滿(mǎn)，才能開(kāi)始填充下一層，這就保證了不需要對(duì)數(shù)組整體進(jìn)行大片的移動(dòng)。這也是隨機(jī)存儲(chǔ)結(jié)構(gòu)（數(shù)組）的短板：刪除一個(gè)元素之后，整體往前移是比較費(fèi)時(shí)的。這個(gè)特性也導(dǎo)致堆在刪除元素的時(shí)候，要把最后一個(gè)葉子節(jié)點(diǎn)補(bǔ)充到樹(shù)根節(jié)點(diǎn)的緣由
關(guān)于JavaScript的幾點(diǎn)小結(jié)
這里是采用面向?qū)ο蟮囊环N實(shí)現(xiàn)方法，感覺(jué)上不是太優(yōu)雅，不知道還有沒(méi)有更好的表示方法和寫(xiě)法；
學(xué)習(xí)了數(shù)組的幾個(gè)用法：push和pop的操作太好用了；
判斷數(shù)組的方式也是臨時(shí)從網(wǎng)上搜的（instanceof），印象不深刻，不用的話下次估計(jì)還是有可能忘掉。
參考
[1]《數(shù)據(jù)結(jié)構(gòu)和算法分析：C語(yǔ)言描述》
[2]圖解數(shù)據(jù)結(jié)構(gòu)（8）——二叉堆
[3]數(shù)據(jù)結(jié)構(gòu)：堆
【堆的javascript實(shí)現(xiàn)方法】相關(guān)文章：
JavaScript類(lèi)定義原型方法的兩種實(shí)現(xiàn)的區(qū)別07-11
JavaScript實(shí)現(xiàn)網(wǎng)頁(yè)刷新代碼段08-07
JavaScript常用方法匯總10-25
javascript編程異常處理的方法08-04
JavaScript fontcolor方法入門(mén)實(shí)例07-07
使用ajax操作JavaScript對(duì)象的方法09-28
堆漆裝飾的技術(shù)方法06-26