Python에서 힙을 확인하는 프로그램이 최대 힙을 형성하는지 여부

힙 트리를 나타내는 목록이 있다고 가정합니다. 우리가 알고 있듯이 힙은 완전한 이진 트리입니다. 요소가 최대 힙을 형성하는지 확인해야 합니다. 최대 힙에 대해 알고 있듯이 모든 요소는 두 하위 요소보다 큽니다.

따라서 입력이 nums =[8, 6, 4, 2, 0, 3]과 같으면 모든 요소가 자식보다 크기 때문에 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=숫자 크기
• 0 ~ n - 1 범위의 i에 대해
  • m :=나는 * 2
  • num :=nums[i]
  • m + 1
  • num
  • 거짓을 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(nums):
   n = len(nums)
   for i in range(n):
      m = i * 2
      num = nums[i]
      if m + 1 < n:
         if num < nums[m + 1]:
            return False
      if m + 2 < n:
         if num < nums[m + 2]:
            return False
   return True

nums = [8, 6, 4, 2, 0, 3]
print(solve(nums))

입력

[8, 6, 4, 2, 0, 3]

출력

True