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