Kiểm tra Max Heap trong Python

Cho danh sách nums, kiểm tra xem nó có biểu diễn max heap không. Tính chất max heap: nút cha ≥ các nút con.

Ví dụ: [5, 3, 4, 1, 2] → True.

Các bước giải quyết

• Duyệt i từ 0 đến len(nums)//2:
  • Nếu nums[i] < nums[2*i+1] → trả về False
  • Nếu 2*i+2 < len(nums) và nums[i] < nums[2*i+2] → trả về False
• Trả về True

Ví dụ mã Python

class Solution:
    def solve(self, nums):
        for i in range(len(nums)//2):
            if not nums[i] >= nums[2*i+1]:
                return False
            if 2*i+2 <= len(nums)-1:
                if not nums[i] >= nums[2*i+2]:
                    return False
        return True

ob = Solution()
nums = [5, 3, 4, 1, 2]
print(ob.solve(nums))

Đầu vào

[5, 3, 4, 1, 2]

Đầu ra

True