是最小堆功能

Question

我想寫一個函數，告訴我給定的列表是否是最小堆。

我至今寫：

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)) 

我不知道的基本情況應該是什麼，是我的遞歸調用正確的嗎？

另外，如何控制索引不會超出範圍？

Answer 1

對於給定的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