堆的javascript實現(xiàn)方法

時間:2024-10-02 05:38:24 JavaScript 我要投稿
  • 相關推薦

堆的javascript實現(xiàn)方法

  堆的定義

  最大(最小)堆是一棵每一個節(jié)點的鍵值都不小于(大于)其孩子(如果存在)的鍵值的樹。大頂堆是一棵完全二叉樹,同時也是一棵最大樹。小頂堆是一棵完全完全二叉樹,同時也是一棵最小樹。

  另外,記住這兩個概念,對寫代碼太重要了:

  1、父節(jié)點和子節(jié)點的關系:看定義

  2、完全二叉樹:參考[2]

  基本操作

  1、Build(構建堆)

  2、Insert(插入)

  3、Delete(刪除:最小或者最大的那個)

  代碼實現(xiàn)

  首先,寫代碼前有兩個非常重要的點:

  1、用一個數(shù)組就可以作為堆的存儲結構,非常簡單而且易操作;

  2、另外同樣因為是數(shù)組作為存儲結構,所以父子節(jié)點之間的關系就能根據(jù)索引就輕松找到對方了。

  對于JavaScript以0作為數(shù)組索引開始,關系如下:

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

  前面提到注意兩個概念,是有助于理解的:

  1、因為是數(shù)組,所以父子節(jié)點的關系就不需要特殊的結構去維護了,索引之間通過計算就可以得到,省掉了很多麻煩。如果是鏈表結構,就會復雜很多;

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

  關于JavaScript的幾點小結

  這里是采用面向對象的一種實現(xiàn)方法,感覺上不是太優(yōu)雅,不知道還有沒有更好的表示方法和寫法;

  學習了數(shù)組的幾個用法:push和pop的操作太好用了;

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

  參考

  [1]《數(shù)據(jù)結構和算法分析:C語言描述》

  [2]圖解數(shù)據(jù)結構(8)——二叉堆

  [3]數(shù)據(jù)結構:堆

【堆的javascript實現(xiàn)方法】相關文章:

JavaScript類定義原型方法的兩種實現(xiàn)的區(qū)別07-11

JavaScript實現(xiàn)網(wǎng)頁刷新代碼段08-07

JavaScript常用方法匯總10-25

JavaScript數(shù)組常用方法介紹09-04

javascript跨域訪問的方法07-09

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

JavaScript fontcolor方法入門實例07-07

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

堆漆裝飾的技術方法06-26

常用排序算法之JavaScript實現(xiàn)代碼段06-04

亚洲制服丝袜二区欧美精品,亚洲精品无码视频乱码,日韩av无码一区二区,国产人妖视频一区二区
日本最新免费的一区二区 | 亚洲中文字幕一级视频电影 | 在线不卡日本ⅴ一区v二区 亚洲成aV人片在线不卡 | 色婷婷综合久久久久中文国产精品 | 日韩精品另类图区中文字幕 | 青青草原国产在线大伊人 |