Computer Science : Binary heap 一問

deepest即係最深, 即係leaf node, 但係唔一定係你o係張圖見到o既leaf node...

圖片參考：http://upload.wikimedia.org/wikipedia/commons/thumb/b/bf/Max-heap.png/240px-Max-heap.png


就第一張圖, 你會見到3下面, 25下面同1下面其實可以放多2個leaf node, 但係冇放, (你幻想呢棵係一棵完整o既樹, 即係有2^n-1咁多個node), 咁佢o地下面o既"leaf node"就冇fill到喇

呢個亦即係last level is not complete, 因為明明呢個最底一層可以放多6個leaf node, 但係冇, complete o既last level有8個

A heap is a complete binary tree where all the nodes are filled with data, and where value of the parent node is smaller than or equal to that of the children.

This is a min-heap in which the root node is the smallest. In a max-heap, the root node has the largest value, and the value of the parent is greater than or equal to that of the children.

In general, a complete binary tree has 2^n-1 nodes, i.e. 1,3,7,15,31...
Where the number of nodes (data) is not exactly equal to 2^n-1, the "empty" nodes must be situated in the deepest level, and on the right.

We can rephrase the preceding paragraph in saying that the filling of the heap is done from left to right, and only if the level is complete can we move on to fill the next level, and in which case we fill from the left to right.

Thus a heap with one node has one level, the top, or the root node.
A heap with two nodes filled has two level, one at the root, and the second one at the left of the second level.
A heap with 10 nodes will be filled successively with 1, 2, 4 nodes at the 1st, 2nd and 3rd levels. 3 nodes on the left of the 4th level will be filled to make 10 nodes.

I have made some explanatory diagrams which are available at the following link:
http://i263.photobucket.com/albums/ii157/mathmate/7008060900110_heap.jpg

Other useful references:
http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic16/
http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E5%A0%86

If you need more information, PM me. I'll be glad to help.