heaps-and-priority-queues

การทำความเข้าใจเกี่ยวกับ Heaps และ Priority Queues

Heaps และ Priority Queues เป็นโครงสร้างข้อมูลที่ใช้ในการจัดการกับค่าที่ต้องการการจัดลำดับตามลำดับความสำคัญ การใช้โครงสร้างข้อมูลเหล่านี้จะช่วยให้การเข้าถึงข้อมูลที่มีลำดับความสำคัญสูงหรือค่ามากที่สุด (หรือค่าน้อยที่สุด) เป็นไปอย่างมีประสิทธิภาพ

---

1. Heaps (ฮีป)

Heap คือโครงสร้างข้อมูลแบบต้นไม้ที่มีลักษณะเป็น Binary Tree ซึ่งแต่ละโหนดของมันมีค่าที่สัมพันธ์กับโหนดอื่นๆ โดยมีการจัดลำดับค่าตามลักษณะ Max-Heap หรือ Min-Heap:

• Max-Heap: ใน Max-Heap ค่าของโหนดพ่อ (Parent Node) จะต้องมีค่ามากกว่าหรือเท่ากับค่าของโหนดลูก (Child Node) ทั้งสองข้าง
• Min-Heap: ใน Min-Heap ค่าของโหนดพ่อจะต้องมีค่าน้อยกว่าหรือเท่ากับค่าของโหนดลูกทั้งสองข้าง

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

• Binary Tree: เป็นต้นไม้ที่มีโหนดทั้งหมดไม่เกินสองลูก
• Complete Binary Tree: ต้นไม้ที่มีโหนดทั้งหมดเต็มที่จากซ้ายไปขวา (ยกเว้นระดับสุดท้ายที่อาจมีบางโหนดหายไป)
• Heap Property: ลำดับค่าของโหนดต้องมีการจัดลำดับตามกฎของ Max-Heap หรือ Min-Heap

การทำงานของ Heap:

• การแทรก (Insert) และการดึงค่าสูงสุดหรือต่ำสุด (Extract) ใน Heap ทำได้ในเวลา O(log n) ซึ่งมีประสิทธิภาพสูงเมื่อเทียบกับการใช้อัลกอริธึมการเรียงลำดับแบบทั่วไป (เช่น O(n log n) ของ Merge Sort)

ตัวอย่างการใช้ Max-Heap:

• Max-Heap: ค่าของโหนดพ่อ (Parent) จะต้องมีค่ามากกว่าหรือเท่ากับค่าของลูก

        100
       /    \
     90      80
    /  \    /   \
  70    60  50    40

• Min-Heap: ค่าของโหนดพ่อ (Parent) จะต้องมีค่าน้อยกว่าหรือเท่ากับค่าของลูก

        10
       /  \
     20    30
    /  \   /  \
  40   50  60  70

ตัวอย่างโค้ดการสร้าง Max-Heap (Python):

import heapq

# สร้าง Max-Heap (โดยการใช้ Min-Heap แล้วใส่ค่าลบ)
def max_heapify(arr):
    return [-x for x in arr]

def insert(heap, value):
    heapq.heappush(heap, -value)  # ใช้ heappush โดยการแปลงเป็นค่าลบเพื่อใช้เป็น Max-Heap

def extract_max(heap):
    return -heapq.heappop(heap)  # ใช้ heappop แล้วกลับค่าลบเพื่อดึงค่ามากที่สุด

# การใช้งาน
arr = [20, 10, 40, 30, 50]
max_heap = max_heapify(arr)
heapq.heapify(max_heap)  # สร้าง Max-Heap จากอาร์เรย์ที่มีอยู่
print(extract_max(max_heap))  # ดึงค่ามากที่สุด (50)

ผลลัพธ์:

50

---

2. Priority Queue (คิวลำดับความสำคัญ)

Priority Queue (PQ) คือโครงสร้างข้อมูลที่คล้ายกับ Queue (คิว) ทั่วไป แต่มีคุณสมบัติพิเศษคือ การเข้าถึงข้อมูลตามลำดับความสำคัญ โดยไม่จำเป็นต้องเป็นลำดับที่มาถึงก่อน (First In First Out, FIFO) แบบคิวปกติ

• เมื่อมีการแทรกข้อมูลลงใน Priority Queue ข้อมูลจะถูกจัดเก็บตามลำดับความสำคัญ
• ค่าที่มีความสำคัญสูงสุด (หรือค่าน้อยสุดในบางกรณี) จะถูกดึงออกมาก่อนเสมอ
• Max-Heap จะใช้สำหรับ Priority Queue ที่มีความสำคัญสูงสุดอยู่ที่ค่ามากที่สุด
• Min-Heap จะใช้สำหรับ Priority Queue ที่มีความสำคัญสูงสุดอยู่ที่ค่าที่น้อยที่สุด

ตัวอย่างการใช้งาน Priority Queue:

ใน Priority Queue เราสามารถใช้โครงสร้าง Heap เป็นพื้นฐานในการดำเนินการ เนื่องจาก Heap จะช่วยให้การแทรกและการดึงข้อมูลที่มีลำดับความสำคัญสูงสามารถทำได้ในเวลา O(log n)

การทำงานของ Priority Queue:

1. Insert: เพิ่มข้อมูลใหม่ลงใน Priority Queue โดยที่ข้อมูลนั้นจะถูกจัดลำดับตามลำดับความสำคัญ
2. Extract: ดึงข้อมูลที่มีความสำคัญสูงสุดออกจากคิว
3. Peek: ดูข้อมูลที่มีความสำคัญสูงสุดโดยไม่ดึงข้อมูลออกจากคิว

ตัวอย่างการใช้งาน Priority Queue (Python):

import heapq

# สร้าง Priority Queue โดยใช้ Min-Heap (ค่าที่น้อยที่สุดจะมีความสำคัญสูงสุด)
pq = []
heapq.heappush(pq, (3, "Task 3"))  # ค่าความสำคัญ (3) และข้อความ
heapq.heappush(pq, (1, "Task 1"))
heapq.heappush(pq, (2, "Task 2"))

# ดูค่าสำคัญสูงสุด
print(heapq.heappop(pq))  # (1, 'Task 1') คือค่าสำคัญสูงสุด

ผลลัพธ์:

(1, 'Task 1')

ข้อดีของ Priority Queue:

• การค้นหาค่าที่มีลำดับความสำคัญสูงสุดและการดึงออกมีประสิทธิภาพ O(log n)
• ใช้งานได้ในหลายสถานการณ์ เช่น การทำงานของ Dijkstra's Algorithm หรือ Huffman Coding

ข้อเสียของ Priority Queue:

• อาจจะต้องใช้หน่วยความจำเพิ่มเติม (เนื่องจากการใช้ Heap หรือ Binary Tree)
• ความเร็วในการค้นหาหรือปรับปรุงค่าของข้อมูลที่มีความสำคัญเฉพาะ (เช่น การค้นหาทั้งหมดในคิว) อาจจะช้ากว่าโครงสร้างข้อมูลอื่นๆ

---

การเปรียบเทียบระหว่าง Heap และ Priority Queue

คุณสมบัติ	Heap	Priority Queue
ลักษณะการทำงาน	โครงสร้างข้อมูลแบบต้นไม้ที่รักษาคุณสมบัติ Max-Heap หรือ Min-Heap	โครงสร้างข้อมูลที่ใช้สำหรับการจัดลำดับความสำคัญ
วิธีการใช้	ใช้ในการจัดการข้อมูลที่มีค่าตามลำดับความสำคัญสูงสุดหรือต่ำสุด	ใช้ในการจัดการคิวที่มีการประมวลผลตามความสำคัญ
การค้นหาค่าที่มีความสำคัญ	สามารถค้นหาค่าที่มีความสำคัญสูงสุด/ต่ำสุดในเวลา O(1)	การดึงค่าที่มีความสำคัญสูงสุด/ต่ำสุดใช้เวลา O(log n)
ความเร็วในการแทรกข้อมูล	เวลา O(log n) สำหรับการแทรกข้อมูล	เวลา O(log n) สำหรับการแทรกข้อมูล
การใช้งาน	ใช้ในการจัดลำดับข้อมูล เช่น การหาค่ามากที่สุดหรือน้อยที่สุด	ใช้ในกรณีที่ต้องการการจัดการคิวตามลำดับความสำคัญ

---

สรุป:

• Heap คือโครงสร้างข้อมูลที่ใช้ในการจัดการข้อมูลแบบต้นไม้ที่สามารถรักษาคุณสมบัติ Max-Heap หรือ Min-Heap ได้
• Priority Queue คือโครงสร้างข้อมูลที่ช่วยในการจัดการกับข้อมูลที่มีลำดับความสำคัญ โดยใช้ Heap เป็นพื้นฐานในการดำเนินการ