堆的定義
最大（最小）堆是一棵每一個節點的鍵值都不小于（大于）其孩子（如果存在）的鍵值的樹。大頂堆是一棵完全二叉樹，同時也是一棵最大樹。小頂堆是一棵完全完全二叉樹，同時也是一棵最小樹。
另外，記住這兩個概念，對寫代碼太重要了：
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]，要求葉子節點從左往右填滿，才能開始填充下一層，這就保證了不需要對數組整體進行大片的移動。這也是隨機存儲結構（數組）的短板：刪除一個元素之后，整體往前移是比較費時的。這個特性也導致堆在刪除元素的時候，要把最后一個葉子節點補充到樹根節點的緣由
代碼實現：
/******************************************************* 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;}// testvar heap = new Heap();heap.build([1, 3, 5, 11, 4, 6, 7, 12, 15, 10, 9, 8]);heap.print();// insertheap.insert(2);heap.print();// deleteheap.delete();heap.print();關于JavaScript的幾點小結
這里是采用面向對象的一種實現方法，感覺上不是太優雅，不知道還有沒有更好的表示方法和寫法；
學習了數組的幾個用法：push和pop的操作太好用了；
判斷數組的方式也是臨時從網上搜的（instanceof），印象不深刻，不用的話下次估計還是有可能忘掉。
參考
[1]《數據結構和算法分析：C語言描述》
[3]>數據結構：堆
總結
JavaScript的數組實現了push和pop這些操作，許多其他語言也提供了類似的數據結構和操作（比如C++的Vector），同時也支持隨機操作。所以，我開始想如果這些結構上簡單的加上自動排序的概念，那么一個堆就輕松搞定了，后面看到C++ STL的make_heap就知道自己知道的太少了，但也慶幸自己思維方式是對的。JavaScript的沒有去查，我想有或者實現起來很容易；
自己去實現了之后，發現這個結構也很簡單，只要你肯去跟它親密接觸一次就可以了；
JavaScript的細節部分還是不太了解，比如數組的應用上還要再翻資料才能用；對于JavaScript的靈魂還是沒有接觸到，精髓部分需要不斷的學習和練習；
這些代碼，只要你去了解了概念，了解了編程的基礎，就可以寫的出來。但是，代碼還可以寫的更簡潔，比如delete函數求最小的子節點的時候，左右節點的索引就不需要比較，肯定是左邊的小。代碼部分感覺還是可以繼續優化和精簡的。
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對武林網的支持。
新聞熱點
疑難解答
