บทเรียน: Heap / Priority Queue
👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ
โครงสร้างที่หยิบค่าน้อยสุด/มากสุดได้เร็ว — เหมาะกับโจทย์ top-K
Heap คือโครงสร้างที่ดูค่าน้อยสุด (min-heap) หรือมากสุด (max-heap) ได้ใน O(1) และเพิ่ม/ลบใน O(log n) เหมาะกับโจทย์ "หา k ตัวที่ใหญ่/เล็กสุด" หรือ "ดึงค่าสุดขั้วซ้ำ ๆ"
ใช้ heapq ใน Python (เป็น min-heap)
python
import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(heapq.heappop(h)) # 1 (น้อยสุดออกก่อน)
# หา k ตัวที่ใหญ่สุด
nums = [3, 1, 5, 12, 2, 11]
print(heapq.nlargest(3, nums)) # [12, 11, 5]เคล็ดลับ max-heap
Python มีแค่ min-heap ถ้าต้องการ max-heap ให้ใส่ค่าติดลบเข้าไป (push -x แล้ว pop ออกมาคูณ -1)
เจอบ่อย
kth largest element, merge k sorted lists, top k frequent elements — เห็นคำว่า "top K" หรือ "k ที่ใกล้ที่สุด" ให้นึกถึง heap ทันที