Max Heap เป็น Python หรือไม่?

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums เราต้องตรวจสอบว่ามันแทนค่า maxheap หรือไม่ เราจะปฏิบัติตามกฎเหล่านี้ -

• nums[i] =nums[2*i + 1] เมื่อ 2*i + 1 อยู่ภายในช่วง
• nums[i] =nums[2*i + 2] เมื่อ 2*i + 2 อยู่ในช่วง

ดังนั้นหากอินพุตเป็น [5, 3, 4, 1, 2] เอาต์พุตจะเป็น True

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

• สำหรับ i ในช่วง 0 ถึง (ขนาดของ nums)/2 ให้ทำ
  • ถ้า nums[i]>=nums[2*i+1] ไม่เป็นจริง ดังนั้น
    • คืนค่าเท็จ
  • ถ้า i*2+2 <=(ขนาดของ nums)-1 แล้ว
    • ถ้า nums[i]>=nums[2*i+2] ไม่เป็นความจริง แล้ว
      • คืนค่าเท็จ
• คืนค่า True

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

[5, 3, 4, 1, 2]

ผลลัพธ์

True