2017-04-11 166 views
0

有人能告诉我哪些是二进制堆(最大值),哪些是最小优先级队列,以及为什么/为什么不是这样?我会在数组中发布它们,因为我不知道如何在这里发布图片,这意味着这个位置是空白的。二进制堆和最小优先级队列的

这里我们去:[8,6,7,4,6​​,6,x],[4,5,4,7,8,4,6],[,4,4,5,7, x,x,6]

我会假设第一个是二进制堆,而另外两个是最小优先级队列,但根据解决方案,我错了。但解决方案可能是错误的,所以如果你知道哪一个是哪个请解释给我。

在此先感谢。

回答

0

那么,第一个可能是一个二进制最大堆。也就是说,树应该是这样的:

  8 
     6  7 
    4 6 6 

第二个是一个二元分堆:

  4 
     5  4 
    7 8 4 6 

第三不能是一个二元堆,因为它不符合形状属性。也就是说,将对应于:

  4 
    4  5 
    7 x x 6 

在二进制堆,最下面一行留下填充。这棵树没有被填满。

所以第一个是二进制最大堆。第二个是二进制最小堆,它也可以被看作是一个面向min的优先级队列。我不知道该怎么称呼第三个。这不是一个有效的最小堆,它不是一个最小优先级队列的顺序表示,因为7在6之前。

至少,这是基于我对二进制堆和优先级队列的理解。