ภาพรวม
Max Heap เป็นโครงสร้างข้อมูลแบบต้นไม้เต็ม (Complete Binary Tree) ที่ค่าของโหนดแม่ (parent) มากกว่าหรือเท่ากับโหนดลูก (children) ทุกคู่ บทความนี้ตรวจสอบว่าลิสต์ตัวเลขที่กำหนดเป็น Max Heap ที่ถูกต้องหรือไม่
เงื่อนไข Max Heap (0-indexed array)
- โหนด i มีลูกซ้ายที่ 2i+1, ลูกขวาที่ 2i+2
- ต้องมี
nums[i] >= nums[2*i+1](ถ้ามีลูกซ้าย) - ต้องมี
nums[i] >= nums[2*i+2](ถ้ามีลูกขวา)
ตัวอย่าง
อินพุต: [5, 3, 4, 1, 2]
โครงสร้าง:
5
/ \
3 4
/ \
1 2
5≥3, 5≥4, 3≥1, 3≥2 → True
โค้ด 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))
รายละเอียดลูป
- วนแค่
len(nums)//2รอบ เพราะโหนดใบ (leaf) ไม่มีลูก ไม่ต้องตรวจสอบ - เช็ค left child เสมอ (เพราะ complete tree)
- เช็ค right child เฉพาะถ้าอยู่ในขอบเขต
ผลลัพธ์
True
