Heap queue (คิวแบบฮีป) เป็นโครงสร้างข้อมูลต้นไม้พิเศษที่แต่ละโหนดผู้ปกครองมีค่าน้อยกว่าหรือเท่ากับโหนดลูกของมัน ใน Python ถูกนำไปใช้ผ่านโมดูล heapq โครงสร้างนี้มีประโยชน์มากสำหรับการสร้าง Priority Queue (คิวลำดับความสำคัญ) ที่รายการที่มีน้ำหนักสูงกว่าจะได้รับการประมวลผลก่อน
การสร้างฮีป (Create a Heap)
ฮีปคิวถูกสร้างโดยใช้ไลบรารีที่มาพร้อมกับ Python ชื่อ heapq ไลบรารีนี้มีฟังก์ชันต่างๆ สำหรับจัดการโครงสร้างข้อมูลฮีป ดังนี้:
- heapify – แปลงลิสต์ทั่วไปให้กลายเป็นฮีป ในฮีปที่ได้ โหนดที่มีค่าน้อยที่สุดจะถูกวางที่ตำแหน่งดัชนี 0 ส่วนข้อมูลอื่นๆ ไม่ได้เรียงลำดับจำเป็น
- heappush – เพิ่มองค์ประกอบเข้าไปในฮีปโดยไม่เปลี่ยนแปลงโครงสร้างฮีปปัจจุบัน
- heappop – นำค่าที่น้อยที่สุดออกจากฮีปและคืนค่ากลับมา
- heapreplace – แทนที่ค่าที่น้อยที่สุดด้วยค่าใหม่ที่ระบุ
ตัวอย่างการสร้างฮีป
ฮีปถูกสร้างโดยการนำลิสต์องค์ประกอบมาผ่านฟังก์ชัน heapify ซึ่งจะจัดเรียงใหม่โดยนำค่าที่น้อยที่สุดไปวางที่ตำแหน่งแรก
โค้ดตัวอย่าง
import heapq
H = [21, 1, 45, 78, 3, 5]
# ใช้ heapify จัดเรียงองค์ประกอบ
heapq.heapify(H)
print(H)ผลลัพธ์
[1, 3, 5, 78, 21, 45]การเพิ่มข้อมูลเข้าไปในฮีป (Inserting into Heap)
การเพิ่มข้อมูลจะวางองค์ประกอบใหม่ที่ตำแหน่งสุดท้ายของลิสต์ แต่สามารถใช้ heapify อีกครั้งเพื่อย้ายค่านั้นไปตำแหน่งแรกได้ หากค่านั้นน้อยที่สุด
โค้ดตัวอย่าง
import heapq
H = [21, 1, 45, 78, 3, 5]
heapq.heapify(H)
print(H)
# เพิ่มค่า 8
heapq.heappush(H, 8)
print(H)ผลลัพธ์
[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]การนำข้อมูลออกจากฮีป (Removing from Heap)
ใช้ heappop เพื่อนำองค์ประกอบที่อยู่ตำแหน่งแรก (ค่าน้อยที่สุด) ออกจากฮีป
โค้ดตัวอย่าง
import heapq
H = [21, 1, 45, 78, 3, 5]
heapq.heapify(H)
print(H)
heapq.heappop(H)
print(H)ผลลัพธ์
[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]การแทนที่ค่าในฮีป (Replacing in a Heap)
ฟังก์ชัน heapreplace จะนำค่าที่น้อยที่สุดออกและแทรกค่าใหม่เข้าไปในตำแหน่งที่เหมาะสมตามกฎฮีป
โค้ดตัวอย่าง
import heapq
H = [21, 1, 45, 78, 3, 5]
heapq.heapify(H)
print(H)
heapq.heapreplace(H, 6)
print(H)ผลลัพธ์
[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]