Chương trình kiểm tra heap có hình thành tối đa heap hay không trong Python

Giả sử chúng ta có một danh sách đại diện cho một cây đống. Như chúng ta biết heap là một cây nhị phân hoàn chỉnh. Chúng ta phải kiểm tra xem các phần tử có đang tạo thành đống tối đa hay không. Như chúng ta biết đối với đống tối đa, mọi phần tử đều lớn hơn cả hai phần tử con của nó.

Vì vậy, nếu đầu vào giống như nums =[8, 6, 4, 2, 0, 3], thì đầu ra sẽ là True vì tất cả các phần tử đều lớn hơn phần tử con của chúng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums
• đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
  • m:=i * 2
  • num:=nums [i]
  • nếu m + 1
  • nếu num
  • trả về Sai

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

True