Heap ใน Data Structures - การแทรกข้อมูลใน Max Heap

 

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

 

Heap คืออะไร?

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

Heap แบ่งออกเป็นสองประเภทหลัก ๆ คือ Max Heap และ Min Heap:

- Max Heap: โหนดพ่อแม่จะมีค่ามากกว่า หรือเท่ากับ โหนดลูกเสมอ - Min Heap: โหนดพ่อแม่จะมีค่าน้อยกว่า หรือเท่ากับ โหนดลูกเสมอ

 

Max Heap ในการเขียนโปรแกรม

Max Heap มักถูกใช้ในงานที่ต้องการดึงค่าที่มากที่สุดออกมาได้อย่างรวดเร็ว เช่นการสร้าง Priority Queue หรือการจัดลำดับข้อมูลอย่าง Heapsort ในบทความนี้เราจะมาศึกษาเกี่ยวกับการแทรกข้อมูลใน Max Heap กัน

 

การแทรกข้อมูลใน Max Heap

การแทรกข้อมูลใน Max Heap ต้องทำตามกฎที่กล่าวไปแล้ว คือโหนดพ่อแม่ต้องมีค่ามากกว่าโหนดลูก ซึ่งวิธีการแทรกมีขั้นตอนดังนี้:

1. เพิ่มข้อมูลในตำแหน่งใบใหม่: เริ่มต้นด้วยการเพิ่มข้อมูลที่ต้องการแทรกในตำแหน่งใบใหม่สุดของต้นไม้ เพื่อรักษาคุณสมบัติ Complete Binary Tree

2. Up-Heapify (Percolate Up): ตรวจสอบค่ากับโหนดพ่อแม่ ถ้าค่าในโหนดที่เพิ่มมีค่ามากกว่า ให้สลับที่กับโหนดพ่อแม่ ทำเช่นนี้ซ้ำจนกว่าจะได้โครงสร้างที่คงคุณสมบัติ Max Heap

 

ตัวอย่างการแทรกข้อมูลใน Max Heap

ลองพิจารณา Max Heap ที่มีโหนดดังนี้:

        50
       /  \
     30   40
    / \
   10  20

และเราต้องการแทรกค่า `45`:

1. เพิ่มข้อมูลในตำแหน่งใหม่: ใบใหม่สุดคือใต้ `40` ดังนั้นเราจะเพิ่ม `45` ตรงนั้น

        50
       /  \
     30   40
    / \   /
   10  20 45

2. Up-Heapify: สลับ `45` กับ `40` เพราะ `45` มีค่ามากกว่า

        50
       /  \
     30   45
    / \   /
   10  20 40

ขณะนี้โครงสร้างได้รักษาคุณสมบัติ Max Heap ไว้แล้ว

 

ตัวอย่างโค้ดสำหรับการแทรกข้อมูล

โค้ดต่อไปนี้เป็นตัวอย่างของการแทรกข้อมูลใน Max Heap ที่ถูกเขียนในภาษา Python:

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

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

    def _up_heapify(self, index):
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[index] > self.heap[parent_index]:
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            self._up_heapify(parent_index)

# ใช้งาน
max_heap = MaxHeap()
max_heap.insert(50)
max_heap.insert(30)
max_heap.insert(40)
max_heap.insert(10)
max_heap.insert(20)
max_heap.insert(45)
print(max_heap.heap)  # Output: [50, 30, 45, 10, 20, 40]

 

ประโยชน์ของ Max Heap

1. การเข้าถึงข้อมูลที่มากที่สุดได้รวดเร็ว: Max Heap ช่วยให้การนำค่าที่มากที่สุดออกมาใช้มีความซับซ้อนแค่ O(1) 2. การใช้งานในอัลกอริทึมต่าง ๆ: เช่น Heapsort ที่ใช้ประโยชน์จากการที่ Heap สามารถจัดเรียงค่าภายในได้ 3. การจัดการ Priority Queue: ซึ่งเป็นการเรียงลำดับค่าโดยใช้ค่าที่มากที่สุดเป็นหลัก

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

 

 

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

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