최소 힙 함수입니다.

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