DIV CSS 佈局教程網

詳解堆(Heap)的 JavaScript 實作方法
編輯:關於JavaScript     

堆的定義

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

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

      1、父節點與子節點的關係:見定義。

      2、完全二叉樹:葉子節點需從左往右填滿,才能開始填下一層。

基本操作

      1、Build(建立堆)

      2、Insert(插入)

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

程式碼實作

首先,寫程式前有兩個重點:

      1、用一個陣列就能作為堆的儲存結構,簡單又易操作;

      2、同樣因為用陣列儲存,父子節點之間的關係能根據索引輕鬆找到對方。

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

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

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

       1、因為是陣列,父子節點的關係不需特別的結構維護,索引之間透過計算即可得到,省下不少麻煩;若用鏈表結構則會複雜許多。

       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]數據結構:堆

總結

JavaScript 的陣列實作了 push、pop 等操作,許多其他語言也提供類似的結構與操作(如 C++ 的 Vector),同時也支援隨機存取。因此我一開始想:若在這些結構上簡單加上自動排序的概念,堆就能輕鬆搞定;後來看到 C++ STL 的 make_heap,才發現自己懂得太少,但也慶幸自己的思路是對的。JavaScript 是否已有類似實作我沒去查,但想必有,或實作起來很容易。親手實作之後,發現這個結構其實很簡單,只要你肯與它近距離接觸一次即可。當然,程式碼還能寫得更簡潔,例如 delete 函數求最小子節點時,左右節點的索引其實不需比較,左邊一定較小。

以上就是這篇文章的全部內容,希望對大家的學習或工作帶來幫助。若有疑問歡迎留言交流,謝謝大家的支持。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved