最小堆的最大深度

Question

考虑一个包含从 1 到 1023 的所有整数恰好一次的最小堆。如果root在深度0，那么9能出现的最大深度是？ 问题的答案是8。

But, considering that a min heap is a nearly complete BT with-

1) for d <- 0 to h-1, all levels have 2^d nodes.

2) for d <- h, nodes are filled from left.

Source:http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/nearly_complete.pdf

错误的答案是4，因为层序遍历是{1,2 3,4 5 6,7 8 9...}

Answer 1

min-heap 需要放置大于其 parent 节点的元素。

考虑到这个问题，可以把1作为根，然后把2作为它的左边child，任何大于9的元素（比如512）作为它的右边child.For2，可以继续这样，将 3 放在左边 child，将 513 放在右边 child。最终获得的最小堆将是 -

                   1
                  / \
                 /   \
                2     512
               / \      /\
              /   \    /  \
             3   513  514  515
            /\    /\   /\   /\
           /  \  
          4  516  .  .  .  .  .  . 
         /   / \ /\  /\ /\ /\ /\ /\
        5   .  . ..  .. .. .. .. ...
       /   /\ /\ /\/\
      6   . . . . ........................... 
     /
    7 .......................................................
   /   
  8 ......................................................
 /
9

圆点表示填充级别，可以用 [517,758] 中的元素替换，因为级别必须填充。

9的深度是8

最小堆的最大深度

Maximum depth of a min heap

heap

data-structures