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

เมื่อพูดถึงโครงสร้างข้อมูล (Data Structures) ที่มีประสิทธิภาพในการจัดการลำดับชั้นของข้อมูล "Heap" เป็นหนึ่งในหัวข้อที่น่าสนใจและมีความสำคัญในวงการเขียนโปรแกรม โดยเฉพาะในการจัดการข้อมูลที่ต้องการเข้าถึงซ้ำๆ ในรูปแบบที่มีลำดับ เช่น คิวจัดอันดับ (Priority Queue) และการจัดเรียงข้อมูล (Sorting)

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

ความเข้าใจพื้นฐานเกี่ยวกับ Heap

Heap คือ โครงสร้างข้อมูลที่มีลักษณะเป็นต้นไม้ทวิภาค (Binary Tree) ซึ่งมีสองรูปแบบหลักๆ ได้แก่ Max Heap และ Min Heap โดยที่:

ทั้งสองรูปแบบนี้ใช้คุณสมบัติที่เรียกว่า "คุณสมบัติของ Heap" (Heap Property) เพื่อจัดการและจัดเรียงข้อมูลภายใน

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

สำหรับ Min Heap:

- โหนดราก (Root Node) จะมีค่าน้อยที่สุดใน Heap

- ในแต่ละโหนด โหนดหลักจะมีค่าน้อยกว่าหรือเท่ากับโหนดลูก

ตัวอย่างโครงสร้าง Min Heap:

       10
      /  \
     15   20
    / \
   30  40

จากตัวอย่างข้างต้น 10 เป็นโหนดรากและมีค่าน้อยกว่าทุกโหนดอื่น ๆ ใน Heap

การสร้าง Min Heap

การสร้าง Min Heap สามารถทำได้ด้วยการแทรกค่าใหม่ที่ต้องการลงในโครงสร้าง โดยมีขั้นตอนดังนี้:

1. เพิ่มค่าใหม่ลงในตำแหน่งถัดไปที่ว่างใน Heap เพื่อรักษาโครงสร้างต้นไม้เต็ม (Complete Binary Tree) เอาไว้

2. ตรวจสอบและปรับเปลี่ยนตำแหน่ง (Heapify) เริ่มจากโหนดที่เพิ่มขึ้นไปทางโหนดรากจนกว่าจะเป็นไปตามคุณสมบัติของ Min Heap

โค้ดตัวอย่างในการสร้าง Min Heap

เพื่อให้เข้าใจได้ง่ายขึ้น มาดูโค้ดตัวอย่างที่แสดงการสร้าง Min Heap ด้วยภาษา Python:

class MinHeap:
    def __init__(self):
        self.heap = []

    def parent(self, i):
        return (i - 1) // 2

    def insert(self, key):
        self.heap.append(key)
        self._heapify_up(len(self.heap) - 1)

    def _heapify_up(self, index):
        while index != 0 and self.heap[self.parent(index)] > self.heap[index]:
            # Swap if the parent node is greater than the current node
            self.heap[self.parent(index)], self.heap[index] = self.heap[index], self.heap[self.parent(index)]
            index = self.parent(index)

    def extract_min(self):
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        root = self.heap[0]
        last_element = self.heap.pop()
        self.heap[0] = last_element
        self._heapify_down(0)
        return root

    def _heapify_down(self, index):
        smallest = index
        left = 2 * index + 1
        right = 2 * index + 2

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left
        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right
        if smallest != index:
            # Swap if the smallest is not the current index
            self.heap[smallest], self.heap[index] = self.heap[index], self.heap[smallest]
            self._heapify_down(smallest)

# ตัวอย่างการใช้งาน
heap = MinHeap()
heap.insert(10)
heap.insert(20)
heap.insert(15)
heap.insert(40)
heap.insert(30)

print("Min:", heap.extract_min())  # Output: Min: 10

จากโค้ดตัวอย่างด้านบน เราได้สร้างคลาส `MinHeap` ที่มีฟังก์ชันการเพิ่มและตัวดึงค่าออกจาก Min Heap โดยใช้การทำงานผ่าน `_heapify_up` และ `_heapify_down` เพื่อรักษาคุณสมบัติของ Min Heap

กรณีการใช้งาน Min Heap

Min Heap เป็นโครงสร้างสำคัญที่มีบทบาทหลากหลายในแอปพลิเคชันต่าง ๆ อาทิ:

การเรียนรู้และเข้าใจการใช้งาน Min Heap เป็นพื้นฐานสำคัญที่ช่วยให้นักพัฒนามีทักษะในการจัดการข้อมูลเชิงลำดับที่มีประสิทธิภาพ

หวังว่าบทความนี้จะช่วยให้คุณมีความเข้าใจเพิ่มเติมเกี่ยวกับ Min Heap และวิธีการประยุกต์ใช้ในงานจริง นอกจากนี้ หากคุณสนใจที่จะศึกษาและฝึกฝนเพิ่มเติมเกี่ยวกับโครงสร้างข้อมูลและการเขียนโปรแกรม สามารถพิจารณาลงทะเบียนเรียนกับ Expert Programming Tutor (EPT) ซึ่งจะช่วยให้คุณได้พัฒนาทักษะด้านวิศวกรรมซอฟต์แวร์ไปอีกขั้น

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

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