當前位置:才華齋>設計>網頁設計>

堆的javascript實現方法

網頁設計 閱讀(1.65W)

堆的定義

堆的javascript實現方法

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

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

1、父節點和子節點的關係:看定義

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

基本操作

1、Build(構建堆)

2、Insert(插入)

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

程式碼實現

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

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

2、另外同樣因為是陣列作為儲存結構,所以父子節點之間的關係就能根據索引就輕鬆找到對方了。

對於JavaScript以0作為陣列索引開始,關係如下:

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

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

1、因為是陣列,所以父子節點的關係就不需要特殊的結構去維護了,索引之間通過計算就可以得到,省掉了很多麻煩。如果是連結串列結構,就會複雜很多;

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

關於JavaScript的幾點小結

這裡是採用面向物件的一種實現方法,感覺上不是太優雅,不知道還有沒有更好的表示方法和寫法;

學習了陣列的幾個用法:push和pop的操作太好用了;

判斷陣列的方式也是臨時從網上搜的(instanceof),印象不深刻,不用的話下次估計還是有可能忘掉。

參考

[1]《資料結構和演算法分析:C語言描述》

[2]圖解資料結構(8)——二叉堆

[3]資料結構:堆