我想编写一个函数来告诉我给定的列表是否是最小堆。
到目前为止我所写的内容：
def is_min_heap(L):
return _is_min_heap(L, 0)
def _is_min_heap(L, i):
if
#base case
else:
return (L[i] < L[2*i+1] and _is_min_heap(L, 2*i+1)) and (L[i] < L[2*i+2] and _is_min_heap(L, 2*1+2))
我不确定基本情况应该是什么以及我的递归调用是否正确？
另外，如何控制索引最终不会超出范围？
对于给定的情况，您有三种不同的情况i：要么你有两个孩子，在这种情况下，你需要检查两个孩子的堆属性，并递归检查两个子树；或者你只有一个孩子，在这种情况下你只需要检查那个孩子；或者你没有孩子，即i是一片叶子，它本身始终是一个有效的堆。
您可以通过检查子项的索引是否仍在列表范围内来检查子项是否存在。
def _is_min_heap(L, i):
l, r = 2 * i + 1, 2 * i + 2
if r < len(L): # has left and right children
if L[l] < L[i] or L[r] < L[i]: # heap property is violated
return False
# check both children trees
return _is_min_heap(L, l) and _is_min_heap(L, r)
elif l < len(L): # only has left children
if L[l] < L[i]: # heap property is violated
return False
# check left children tree
return _is_min_heap(L, l)
else: # has no children
return True
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
