詳解堆的javascript實作方法

堆的定義

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

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

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

      2、完全二叉樹：參考[2] 
      1、Build（建置堆）

      2、Insert(插入）

     有兩個非常重要的點：

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

      2、另外同樣因為是數組節點之間的關係輕鬆找到對方了。

對於JavaScript以0作為數組索引開始，關係如下：

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

   

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

   就不需要特殊的結構去維護了，索引之間透過計算就可以得到，省掉了許多麻煩。如果是鍊錶結構，就會複雜很多；

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

程式碼實作：

/******************************************************
* file : 堆
* author : "page"
* time : "2016/11/02"
*******************************************************/
function Heap()
{
 this.data = [];
}
 
Heap.prototype.print = function () {
 console.log("Heap: " + this.data);
}
 
Heap.prototype.build = function(data){
 // 初始化
 this.data = [];
 if (!data instanceof Array)
 return false;
 
 // 入堆
 for (var i = 0; i < data.length; ++i) {
 this.insert(data[i]);
 }
 
 return true;
}
 
Heap.prototype.insert = function( nValue ){
 if (!this.data instanceof Array) {
 this.data = [];
 }
 
 this.data.push(nValue);
 // 更新新节点
 var nIndex = this.data.length-1;
 var nFatherIndex = Math.floor((nIndex-1)/2);
 while (nFatherIndex > 0){
 if (this.data[nIndex] < this.data[nFatherIndex]) {
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nFatherIndex];
 this.data[nFatherIndex] = temp;
 }
 
 nIndex = nFatherIndex;
 nFatherIndex = Math.floor((nIndex-1)/2);
 }
}
 
Heap.prototype.delete = function( ){
 if (!this.data instanceof Array) {
 return null;
 }
 
 var nIndex = 0;
 var nValue = this.data[nIndex];
 var nMaxIndex = this.data.length-1;
 // 更新新节点
 var nLeaf = this.data.pop();
 this.data[nIndex] = nLeaf;
 
 while (nIndex < nMaxIndex ){
 var nLeftIndex = 2 * (nIndex+1) - 1;
 var nRightIndex = 2 * (nIndex+1);
 
 // 找最小的一个子节点(nLeftIndex < nRightIndex)
 var nSelectIndex = nLeftIndex;
 if (nRightIndex < nMaxIndex) {
 nSelectIndex = (this.data[nLeftIndex] > this.data[nRightIndex]) ? nRightIndex : nLeftIndex;
 }
 
 if (nSelectIndex < nMaxIndex && this.data[nIndex] > this.data[nSelectIndex] ){
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nSelectIndex];
 this.data[nSelectIndex] = temp;
 }
 
 nIndex = nSelectIndex;
 }
 
 return nValue;
}
// test
var heap = new Heap();
heap.build([1, 3, 5, 11, 4, 6, 7, 12, 15, 10, 9, 8]);
heap.print();
// insert
heap.insert(2);
heap.print();
// delete
heap.delete();
heap.print();

   

關於JavaScript的幾點小結物件的一種實現方法，感覺上不是太優雅，不知道還有沒有更好的表示方法和寫法；

學習了數組的幾個用法：push和pop的操作太好用了；

判斷陣列的方式也是暫時從網路上搜的（instanceof），印像不深刻，不用的話下次估計還是有可能忘記。

參考

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

[2]圖解資料結構（8）－二叉堆

[3]>資料結構：堆疊

總結

[3]>資料結構：堆疊

總結

[3]>資料結構：堆疊

總結

JavaScript的陣列實作了push和pop這些操作，許多其他語言也提供了類似的資料結構和操作（例如C++的Vector），同時也支援隨機操作。所以，我開始想如果這些結構上簡單的加上自動排序的概念，那麼一個堆就輕鬆搞定了，後面看到C++ STL的make_heap就知道自己知道的太少了，但也慶幸自己思維方式是對的。 JavaScript的沒有去查，我想有或實現起來很容易；

自己去實現了之後，發現這個結構也很簡單，只要你肯去跟它親密接觸一次就可以了；

JavaScript的細節部分還是不太了解，例如數組的應用上還要再翻資料才能用；對於JavaScript的靈魂還是沒有接觸到，精髓部分需要不斷的學習和練習；

這些代碼，只要你去了解了概念，了解了編程的基礎，就可以寫出來的。但是，程式碼還可以寫的更簡潔，例如delete函數求最小的子節點的時候，左右節點的索引就不需要比較，肯定是左邊的小。程式碼部分感覺還是可以繼續優化和精簡的。