โปรแกรมตรวจสอบฮีปกำลังสร้างฮีปสูงสุดหรือไม่ใน Python

สมมติว่าเรามีรายการที่แสดงถึงฮีปทรี ดังที่เรารู้ว่าฮีปเป็นต้นไม้ไบนารีที่สมบูรณ์ เราต้องตรวจสอบว่าองค์ประกอบนั้นสร้างฮีปสูงสุดหรือไม่ อย่างที่เราทราบสำหรับ max heap ทุกองค์ประกอบมีขนาดใหญ่กว่าลูกของมันทั้งคู่

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[8, 6, 4, 2, 0, 3] ผลลัพธ์จะเป็น True เพราะองค์ประกอบทั้งหมดมีขนาดใหญ่กว่ารายการย่อย

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ nums
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • ม :=ผม * 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