Pages

2011年4月17日 星期日

[演算法] heap

(1) 建立一個heap,矩陣的index跟heap從root由上往下由左往右數的index相同。

(2) 高度定義為heap中某個node由上往下找最常路徑到達leaf所經過的edge數。

(3) 由等比數列可知,n個元素的heap其高度為floor(lg n)。因為:
2^h <= n <= 2^(h+1) – 1

(4) heap中,假設陣列index從1開始數且陣列大小為n個元素,index為floor(n/2) + 1開始的node都是leaf。所以在建立heap的時候,要從index為floor(n/2)開始的node一直到index為1的node,將每個node調整為符合max-heap或min-heap的特性。

(5) min heap可以應用在Huffman code上,剛好我這次通訊模擬作業有講到這種編碼在通訊的應用,不過我還不熟悉這種編碼的演算法,只知道此編碼可以壓縮資料。

沒有留言:

張貼留言