ในส่วนนี้เราจะดูวิธีรวมสอง sorted lists โดยใช้โมดูล heapq ใน Python ตัวอย่าง: list1 = [10, 20, 30, 40] และ list2 = [100, 200, 300, 400, 500] หลังรวมจะได้ [10, 20, 30, 40, 100, 200, 300, 400, 500]
โมดูล heapq เป็น standard library ไม่ต้องติดตั้งเพิ่ม
เมธอดสำคัญของ heapq
| เมธอด | คำอธิบาย |
|---|---|
heapify(iterable) | แปลง iterable เป็น heap (in-place) |
heappush(heap, item) | เพิ่ม item ลง heap แล้ว heapify ใหม่ |
heappop(heap) | นำ item ที่น้อยที่สุดออกจาก heap (root) |
heappushpop(heap, item) | push แล้ว pop ทีเดียว (มีประสิทธิภาพกว่า) |
heapreplace(heap, item) | pop แล้ว push ทีเดียว (ต่างจากข้างบนลำดับ) |
nlargest(n, iterable) | คืน n ตัวที่มากที่สุด |
nsmallest(n, iterable) | คืน n ตัวที่น้อยที่สุด |
merge(*iterables) | รวม sorted iterables หลายตัวเป็น iterator เดียว (sorted) |
โค้ดตัวอย่าง: ใช้ heapq.merge()
import heapq
first_list = [45, 12, 63, 95, 74, 21, 20, 15, 36]
second_list = [42, 13, 69, 54, 15]
# เรียงลำดับก่อน (heapq.merge ต้องการ input ที่เรียงแล้ว)
first_list = sorted(first_list)
second_list = sorted(second_list)
print('First sorted list:', first_list)
print('Second sorted list:', second_list)
# merge คืนค่า iterator ต้อง list() เพื่อดูผล
final_list = list(heapq.merge(first_list, second_list))
print('The final merged list:', final_list)
ผลลัพธ์
First sorted list: [12, 15, 20, 21, 36, 45, 63, 74, 95]
Second sorted list: [13, 15, 42, 54, 69]
The final merged list: [12, 13, 15, 15, 20, 21, 36, 42, 45, 54, 63, 69, 74, 95]
คำอธิบาย heapq.merge()
- รับ หลาย sorted iterables (ไม่จำกัด 2 ตัว)
- คืนค่า iterator (lazy evaluation) ไม่สร้างลิสต์ใหม่ทันที
- ใช้ heap ด้านใน ทำให้ memory efficient
- ความซับซ้อน O(n log k) โดย n = total elements, k = จำนวน iterables
- เหมือน merge step ใน merge sort
ตัวอย่างเพิ่มเติม: รวม 3 ลิสต์
a = [1, 4, 7]
b = [2, 5, 8]
c = [3, 6, 9]
merged = list(heapq.merge(a, b, c))
print(merged) # [1, 2, 3, 4, 5, 6, 7, 8, 9]
สรุป: heapq.merge() เป็นวิธีมาตรฐานและมีประสิทธิภาพสำหรับรวม sorted sequences หลายตัวใน Python
