โปรแกรมตรวจสอบว่าฮีปเป็น Max Heap หรือไม่ใน Python

สมมติว่าเรามีรายการที่แสดงต้นไม้ฮีป (heap tree) ฮีปคือต้นไม้ไบนารีสมบูรณ์ (complete binary tree) เราต้องตรวจสอบว่าสมาชิกจัดเรียงเป็น Max Heap หรือไม่ ตามนิยามของ Max Heap ทุกสมาชิกต้องมีค่ามากกว่าลูกทั้งสองของมัน

เช่น ถ้าอินพุตคือ nums = [8, 6, 4, 2, 0, 3] ผลลัพธ์จะเป็น True เพราะทุกสมาชิกมีค่ามากกว่าลูกของมัน

ขั้นตอนการแก้ปัญหา

1. n := ขนาดของ nums
2. สำหรับ i ในช่วง 0 ถึง n-1:
   • m := i * 2
   • num := nums[i]
   • ถ้า m + 1 < n และ num < nums[m + 1] คืนค่า False
   • ถ้า m + 2 < n และ num < nums[m + 2] คืนค่า False
3. คืนค่า True

ตัวอย่างการใช้งาน

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