โมดูล heapq ให้ Min-Heap Implementation (Priority Queue) บน List ทำให้ Pop Minimum ได้ O(log n)
import heapq
หลักการ Min-Heap
- Root = Minimum Element (Priority 1 = สูงสุด)
- Parent ≤ Children เสมอ
- เก็บใน List แบบ Complete Binary Tree
ฟังก์ชันหลัก
| Function | คำอธิบาย | Complexity |
|---|---|---|
heapify(x) | แปลง List -> Heap (In-place) | O(n) |
heappush(heap, item) | Push Item + Re-heap | O(log n) |
heappop(heap) | Pop & Return Min Item + Re-heap | O(log n) |
heappushpop(heap, item) | Push แล้ว Pop (Atomic, Fast) | O(log n) |
heapreplace(heap, item) | Pop แล้ว Push (Atomic, Fast) | O(log n) |
nlargest(n, iterable, key=None) | N Largest Elements | O(n log k) |
nsmallest(n, iterable, key=None) | N Smallest Elements | O(n log k) |
โค้ดตัวอย่าง
import heapq
data = [58, 41, 12, 17, 89, 65, 23, 20, 10, 16, 17, 19]
# 1. Heapify
heapq.heapify(data)
print("Heapified:", data)
# [10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
# 2. Push
heapq.heappush(data, 7)
print("After push 7:", data)
# [7, 16, 10, 17, 17, 12, 23, 20, 41, 89, 58, 65, 19]
# 3. Pop
popped = heapq.heappop(data)
print(f"Popped: {popped}, Heap: {data}")
# Popped: 7
# 4. nlargest / nsmallest
print("4 Largest:", heapq.nlargest(4, data))
print("3 Smallest:", heapq.nsmallest(3, data))
ผลลัพธ์
Heapified: [10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65] After push 7: [7, 16, 10, 17, 17, 12, 23, 20, 41, 89, 58, 65, 19] Popped: 7 Heap: [10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65] 4 Largest: [89, 65, 58, 41] 3 Smallest: [10, 12, 16]
Priority Queue Pattern (Tuple: Priority, Data)
import heapq
pq = []
heapq.heappush(pq, (2, 'Low Priority Task'))
heapq.heappush(pq, (1, 'High Priority Task'))
heapq.heappush(pq, (3, 'Background Task'))
while pq:
priority, task = heapq.heappop(pq)
print(f"Priority {priority}: {task}")
# Output:
# Priority 1: High Priority Task
# Priority 2: Low Priority Task
# Priority 3: Background Task
Max-Heap (Python มีแค่ Min-Heap)
# วิธี 1: Negate Values
max_heap = []
for x in [5, 1, 9, 3]:
heapq.heappush(max_heap, -x)
print(-heapq.heappop(max_heap)) # 9
# วิธี 2: Custom Key (Python 3.11+)
# heapq.heappush(heap, item, key=lambda x: -x)
การประยุกต์ใช้จริง
- Dijkstra/A* Pathfinding: Priority Queue
- Task Scheduler: Cron-like, Delayed Execution
- Streaming Top-K: nlargest/nsmallest บน Data Stream
- Huffman Coding: Merge Smallest Frequencies
- K-way Merge: Merge K Sorted Lists
K-way Merge Example
import heapq
def merge_k_sorted(lists):
heap = []
for i, lst in enumerate(lists):
if lst:
heapq.heappush(heap, (lst[0], i, 0))
result = []
while heap:
val, list_idx, elem_idx = heapq.heappop(heap)
result.append(val)
if elem_idx + 1 < len(lists[list_idx]):
next_val = lists[list_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
return result
print(merge_k_sorted([[1,4,7], [2,5,8], [3,6,9]]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
