Heap ใน Data Structures - การสร้าง Max Heap

ในโลกของการเขียนโปรแกรมและการพัฒนาซอฟต์แวร์นั้น การจัดการข้อมูลที่มีประสิทธิภาพถือเป็นหัวใจสำคัญที่นำไปสู่ความสำเร็จ การทำความเข้าใจในโครงสร้างข้อมูลต่างๆ เช่น Stack, Queue, Linked List และ Heap จะช่วยให้นักพัฒนาสามารถออกแบบอัลกอริทึมที่รวดเร็วและมีประสิทธิภาพ

หนึ่งในโครงสร้างข้อมูลที่น่าสนใจและถูกใช้อย่างแพร่หลายในปัจจุบันคือ "Heap" ซึ่งในบทความนี้เราจะมาเจาะลึกถึง Max Heap รวมถึงวิธีการสร้างและการนำไปใช้ในกรณีต่างๆ

ทำความรู้จักกับ Heap

Heap เป็นโครงสร้างข้อมูลที่มีคุณสมบัติพิเศษ โดยถูกสร้างขึ้นในรูปแบบของ Binary Tree ซึ่งมีสองประเภทหลักคือ Max Heap และ Min Heap สำหรับ Max Heap คุณสมบัติที่สำคัญคือ โหนดหรือค่าบนสุดเสมอจะมีค่ามากที่สุดในกลุ่มของโหนดลูกๆ

ตัวอย่างการจัดเรียงข้อมูลในรูปแบบ Max Heap:

     90
    /   \
  85     80
 /  \   /  \
60  70 75  50

คุณสมบัติของ Max Heap

1. เป็น Complete Binary Tree: หมายความว่า ทุกระดับของต้นไม้ย่อยจะถูกเติมเต็มจากซ้ายไปขวาอย่างสมบูรณ์

2. Parent Node มากกว่า Child Node: ค่าของโหนดใดๆ จะต้องมีค่ามากกว่าโหนดลูกของมันเสมอ

การสร้าง Max Heap

ขั้นตอนการสร้าง Max Heap

การสร้าง Max Heap จากอาร์เรย์หรือชุดข้อมูลเริ่มต้นนั้น เราจะใช้กระบวนการที่เรียกว่า "Heapify" ซึ่งทำงานโดยการปรับโครงสร้างของข้อมูลให้เทียบเท่าคุณสมบัติของ Max Heap

Heapify Algorithm

1. เริ่มต้นจากโหนดที่ไม่ได้เป็นใบ (Non-leaf Node) โดยนับย้อนจากปลายสุดของอาร์เรย์

2. เปรียบเทียบค่าโหนดนั้นกับโหนดลูกเพื่อสลับที่ถ้าจำเป็น

3. ดำเนินการขั้นตอนที่สองซ้ำๆ กับโหนดที่ลูกถูกสลับไป จนกระทั่งไม่มีการสลับใดๆเหลืออยู่

ตัวอย่างโค้ด

def heapify(arr, n, i):
    largest = i  # กำหนดค่าโหนดปัจจุบันเป็นโหนดใหญ่สุด
    left = 2 * i + 1  # โหนดซ้าย
    right = 2 * i + 2  # โหนดขวา

    # ตรวจสอบว่าโหนดซ้ายใหญ่กว่าโหนดปัจจุบันใหญ่สุดหรือไม่
    if left < n and arr[i] < arr[left]:
        largest = left

    # ตรวจสอบว่าโหนดขวาใหญ่กว่าโหนดปัจจุบันใหญ่สุดหรือไม่
    if right < n and arr[largest] < arr[right]:
        largest = right

    # ถ้าโหนดใหญ่สุดไม่ใช่โหนดปัจจุบัน
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # สลับตำแหน่ง

        # Heapify ต่อไปที่โหนดลูก
        heapify(arr, n, largest)

def buildMaxHeap(arr):
    n = len(arr)
    # สร้าง Max Heap จากโหนดที่ไม่ใช่ใบ
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

# ตัวอย่างการใช้งาน
arr = [3, 9, 2, 1, 4, 5]
buildMaxHeap(arr)
print("Max Heap:", arr)

การใช้งาน Max Heap ในชีวิตจริง

Max Heap มีประโยชน์หลายอย่างในโปรเจกต์ต่างๆ อาทิเช่น:

การทำความเข้าใจและใช้งาน Max Heap จะช่วยให้นักพัฒนาสามารถจัดการกับข้อมูลที่ซับซ้อนได้อย่างมีประสิทธิภาพ นอกจากนี้ยังเปิดโลกโอกาสให้นำโครงสร้างข้อมูลนี้ไปปรับใช้ในสถานการณ์จริงได้หลากหลาย หากคุณกำลังสนใจที่จะเพิ่มพูนความรู้ด้านการเขียนโปรแกรม โครงสร้างข้อมูลเป็นหนึ่งในหัวข้อที่คุณไม่ควรมองข้ามเลยนะครับ

ท้ายสุดนี้ ถ้าคุณต้องการเสริมสร้างทักษะและความรู้ด้านโครงสร้างข้อมูลและการเขียนโปรแกรม สามารถพิจารณาศึกษาที่ EPT (Expert-Programming-Tutor) ที่เรามีคอร์สครอบคลุมให้น้องๆ และผู้ที่สนใจได้ศึกษาอย่างเต็มที่ครับ!

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง

หากเจอข้อผิดพลาด หรือต้องการพูดคุย ติดต่อได้ที่ https://m.me/expert.Programming.Tutor/