堆的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]數據結構:堆
-
網頁設計的佈局
網頁設計的工作目標,是通過使用更合理的顏色、字體、圖片、樣式進行頁面設計美化,在功能限定的情況下,儘可能給予用户完美的視覺體驗。以下是小編為您帶來的網頁設計的佈局,看看吧!網頁設計的佈局11、響應式網頁設計響應式網頁設計是網頁設計的一種技術,可在N多種瀏...
-
網頁設計黃金配色原則是什麼
身為網頁設計新手的你,是不是還在糾結於你製作的網頁找不到一組完美的配色方案?在本教程中我們將與你分享6條肯定會火,並且“錯不了”的指導方針,你可以按照這些原則把握最基本的色彩規律。現在我們分享的這些原則都不是規則,你會在你的職業生涯中創造出更多的配色...
-
Dreamweaver輸入的文本字體怎樣加粗
Dreamweaver輸入的文本字體怎麼加粗?Dreamweaver中想要加粗輸入的文本,該怎麼加粗呢?這都是最基礎的教程,很簡單,需要的朋友可以參考下,下面就跟隨小編一起來看看吧!Dreamweaver怎麼給字體加粗,下面我們就來看看詳細的.教程。1、打開我的軟件2、文件新建一個3、新建...
-
JavaScript基本語法分析
一、JavaScript基本語法。(一)數據類型與變量類型。整數,小數,佈局,字符串,日期時間,數組強制轉換:parseInt()parseFloat()isNaN()(二)數組var數組名=newArray([長度]);//“假冒”數組th-長度a[下標]=值。a[下標](三)函數複製代碼代碼如下:function函數名(形參){}function...