堆的javascript實(shí)現方法

　　堆的定義

　　最大（最�。┒咽且豢妹恳粋�(gè)節點(diǎn)的鍵值都不小于（大于）其孩子（如果存在）的鍵值的樹(shù)。大頂堆是一棵完全二叉樹(shù)，同時(shí)也是一棵最大樹(shù)。小頂堆是一棵完全完全二叉樹(shù)，同時(shí)也是一棵最小樹(shù)。

　　另外，記住這兩個(gè)概念，對寫(xiě)代碼太重要了：

　　1、父節點(diǎn)和子節點(diǎn)的關(guān)系：看定義

　　2、完全二叉樹(shù)：參考[2]

　　基本操作

　　1、Build（構建堆）

　　2、Insert(插入）

　　3、Delete（刪除：最小或者最大的那個(gè)）

　　代碼實(shí)現

　　首先，寫(xiě)代碼前有兩個(gè)非常重要的點(diǎn)：

　　1、用一個(gè)數組就可以作為堆的存儲結構，非常簡(jiǎn)單而且易操作；

　　2、另外同樣因為是數組作為存儲結構，所以父子節點(diǎn)之間的關(guān)系就能根據索引就輕松找到對方了。

　　對于JavaScript以0作為數組索引開(kāi)始，關(guān)系如下：

　　nLeftIndex = 2 * (nFatherIndex+1) - 1;nRightIndex = 2* (nFatherIndex+1);

　　前面提到注意兩個(gè)概念，是有助于理解的：

　　1、因為是數組，所以父子節點(diǎn)的關(guān)系就不需要特殊的結構去維護了，索引之間通過(guò)計算就可以得到，省掉了很多麻煩。如果是鏈表結構，就會(huì )復雜很多；

　　2、完全二叉樹(shù)的概念可以參考[2]，要求葉子節點(diǎn)從左往右填滿(mǎn)，才能開(kāi)始填充下一層，這就保證了不需要對數組整體進(jìn)行大片的移動(dòng)。這也是隨機存儲結構（數組）的短板：刪除一個(gè)元素之后，整體往前移是比較費時(shí)的。這個(gè)特性也導致堆在刪除元素的時(shí)候，要把最后一個(gè)葉子節點(diǎn)補充到樹(shù)根節點(diǎn)的緣由

　　關(guān)于JavaScript的幾點(diǎn)小結

　　這里是采用面向對象的一種實(shí)現方法，感覺(jué)上不是太優(yōu)雅，不知道還有沒(méi)有更好的表示方法和寫(xiě)法；

　　學(xué)習了數組的幾個(gè)用法：push和pop的操作太好用了；

　　判斷數組的方式也是臨時(shí)從網(wǎng)上搜的（instanceof），印象不深刻，不用的話(huà)下次估計還是有可能忘掉。

　　參考

　　[1]《數據結構和算法分析：C語(yǔ)言描述》

　　[2]圖解數據結構（8）——二叉堆

　　[3]數據結構：堆

【堆的javascript實(shí)現方法】相關(guān)文章：

JavaScript類(lèi)定義原型方法的兩種實(shí)現的區別07-11

JavaScript實(shí)現網(wǎng)頁(yè)刷新代碼段08-07

JavaScript常用方法匯總10-25

JavaScript數組常用方法介紹09-04

javascript跨域訪(fǎng)問(wèn)的方法07-09

javascript編程異常處理的方法08-04

JavaScript fontcolor方法入門(mén)實(shí)例07-07

使用ajax操作JavaScript對象的方法09-28

堆漆裝飾的技術(shù)方法06-26

常用排序算法之JavaScript實(shí)現代碼段06-04