Heap & Priority Queue
โครงสร้างที่ดึงค่าน้อยสุด/มากสุดได้เร็ว — เจอบ่อยมากในงานจริงและสัมภาษณ์
heap คือ tree พิเศษที่ "ค่าน้อยสุด (หรือมากสุด) อยู่บนสุดเสมอ" ทำให้ดึงค่านั้นได้เร็ว O(log n) เหมาะกับงานที่ต้องหยิบ "ตัวที่สำคัญที่สุด" ตลอด เช่น คิวงานตามความสำคัญ, หา top-k
heapq — min-heap ของ Python
Python มีโมดูล heapq ที่ทำ min-heap (ค่าน้อยสุดอยู่บน) บน list ปกติ
import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(heapq.heappop(h)) # 1 (น้อยสุดออกก่อนเสมอ)
print(heapq.heappop(h)) # 3
# แปลง list เป็น heap ทันที O(n)
nums = [5, 1, 8, 3]
heapq.heapify(nums)
print(heapq.heappop(nums)) # 1หา top-k / max-heap
heapq เป็น min-heap ถ้าอยากได้ max-heap ให้ใส่ค่าติดลบ; หา k ตัวที่ใหญ่/เล็กสุดมี helper สำเร็จ
import heapq
nums = [5, 1, 8, 3, 9, 2]
print(heapq.nlargest(3, nums)) # [9, 8, 5]
print(heapq.nsmallest(2, nums)) # [1, 2]
# max-heap ด้วยค่าติดลบ
h = []
for n in nums:
heapq.heappush(h, -n)
print(-heapq.heappop(h)) # 9 (มากสุด)Priority Queue
heap ใช้ทำ priority queue — คิวที่หยิบตามความสำคัญ ไม่ใช่ลำดับเข้า ใส่ tuple (priority, item)
import heapq
pq = []
heapq.heappush(pq, (2, "งานปกติ"))
heapq.heappush(pq, (1, "งานด่วน"))
heapq.heappush(pq, (3, "งานไว้ทีหลัง"))
print(heapq.heappop(pq)) # (1, 'งานด่วน') ออกตาม priority น้อยสุดเห็นโจทย์ว่า "หา k ตัวที่ใหญ่/เล็กสุด", "หยิบตัวสำคัญสุดเรื่อย ๆ", "merge หลาย sorted list" → คิดถึง heap การหา top-k ด้วย heap เป็น O(n log k) เร็วกว่า sort ทั้งหมด O(n log n) เมื่อ k เล็ก
สรุปหัวข้อนี้
- heap = ดึงค่าน้อยสุด/มากสุดได้ O(log n)
- heapq: heappush/heappop (min-heap), heapify O(n)
- max-heap ใช้ค่าติดลบ; nlargest/nsmallest หา top-k
- priority queue: push (priority, item) — หยิบตาม priority
1) ใช้ heapq หา 3 ตัวที่มากสุดใน list 2) ทำ priority queue ของงานด้วย tuple (priority, name) 3) ทำ max-heap ด้วยค่าติดลบ 4) อธิบายว่าทำไม heap หา top-k เร็วกว่า sort ทั้งหมดเมื่อ k เล็ก