堆的定義

最大（最?。┒咽且豢妹恳粋€(gè)節(jié)點(diǎn)的鍵值都不小于（大于）其孩子（如果存在）的鍵值的樹。大頂堆是一棵完全二叉樹，同時(shí)也是一棵最大樹。小頂堆是一棵完全完全二叉樹，同時(shí)也是一棵最小樹。

另外，記住這兩個(gè)概念，對(duì)寫代碼太重要了：

      1、父節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系：看定義

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

基本操作

      1、Build（構(gòu)建堆）

      2、Insert(插入）

      3、Delete（刪除：最小或者最大的那個(gè)）

代碼實(shí)現(xiàn)

首先，寫代碼前有兩個(gè)非常重要的點(diǎn)：

      1、用一個(gè)數(shù)組就可以作為堆的存儲(chǔ)結(jié)構(gòu)，非常簡(jiǎn)單而且易操作；

      2、另外同樣因?yàn)槭菙?shù)組作為存儲(chǔ)結(jié)構(gòu)，所以父子節(jié)點(diǎn)之間的關(guān)系就能根據(jù)索引就輕松找到對(duì)方了。

對(duì)于JavaScript以0作為數(shù)組索引開始，關(guān)系如下：

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

前面提到注意兩個(gè)概念，是有助于理解的：

       1、因?yàn)槭菙?shù)組，所以父子節(jié)點(diǎn)的關(guān)系就不需要特殊的結(jié)構(gòu)去維護(hù)了，索引之間通過計(jì)算就可以得到，省掉了很多麻煩。如果是鏈表結(jié)構(gòu)，就會(huì)復(fù)雜很多；

       2、完全二叉樹的概念可以參考[2]，要求葉子節(jié)點(diǎn)從左往右填滿，才能開始填充下一層，這就保證了不需要對(duì)數(shù)組整體進(jìn)行大片的移動(dòng)。這也是隨機(jī)存儲(chǔ)結(jié)構(gòu)（數(shù)組）的短板：刪除一個(gè)元素之后，整體往前移是比較費(fèi)時(shí)的。這個(gè)特性也導(dǎo)致堆在刪除元素的時(shí)候，要把最后一個(gè)葉子節(jié)點(diǎn)補(bǔ)充到樹根節(jié)點(diǎn)的緣由

代碼實(shí)現(xiàn)：

/******************************************************
* 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);
 // 更新新節(jié)點(diǎn)
 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;
 // 更新新節(jié)點(diǎn)
 var nLeaf = this.data.pop();
 this.data[nIndex] = nLeaf;

 while (nIndex < nMaxIndex ){
 var nLeftIndex = 2 * (nIndex+1) - 1;
 var nRightIndex = 2 * (nIndex+1);

 // 找最小的一個(gè)子節(jié)點(diǎn)(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();

關(guān)于JavaScript的幾點(diǎn)小結(jié)

這里是采用面向?qū)ο蟮囊环N實(shí)現(xiàn)方法，感覺上不是太優(yōu)雅，不知道還有沒有更好的表示方法和寫法；

學(xué)習(xí)了數(shù)組的幾個(gè)用法：push和pop的操作太好用了；

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

參考

[1]《數(shù)據(jù)結(jié)構(gòu)和算法分析：C語(yǔ)言描述》

[2]圖解數(shù)據(jù)結(jié)構(gòu)（8）——二叉堆

[3]>數(shù)據(jù)結(jié)構(gòu)：堆

總結(jié)

JavaScript的數(shù)組實(shí)現(xiàn)了push和pop這些操作，許多其他語(yǔ)言也提供了類似的數(shù)據(jù)結(jié)構(gòu)和操作（比如C++的Vector），同時(shí)也支持隨機(jī)操作。所以，我開始想如果這些結(jié)構(gòu)上簡(jiǎn)單的加上自動(dòng)排序的概念，那么一個(gè)堆就輕松搞定了，后面看到C++ STL的make_heap就知道自己知道的太少了，但也慶幸自己思維方式是對(duì)的。JavaScript的沒有去查，我想有或者實(shí)現(xiàn)起來很容易；
自己去實(shí)現(xiàn)了之后，發(fā)現(xiàn)這個(gè)結(jié)構(gòu)也很簡(jiǎn)單，只要你肯去跟它親密接觸一次就可以了；

JavaScript的細(xì)節(jié)部分還是不太了解，比如數(shù)組的應(yīng)用上還要再翻資料才能用；對(duì)于JavaScript的靈魂還是沒有接觸到，精髓部分需要不斷的學(xué)習(xí)和練習(xí)；

這些代碼，只要你去了解了概念，了解了編程的基礎(chǔ)，就可以寫的出來。但是，代碼還可以寫的更簡(jiǎn)潔，比如delete函數(shù)求最小的子節(jié)點(diǎn)的時(shí)候，左右節(jié)點(diǎn)的索引就不需要比較，肯定是左邊的小。代碼部分感覺還是可以繼續(xù)優(yōu)化和精簡(jiǎn)的。

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對(duì)腳本之家的支持。

最新評(píng)論