Heap / Priority Queue — พื้นฐาน & แนวคิด

Heap (ฮีป) หรือที่มักเรียกว่า Priority Queue (คิวลำดับความสำคัญ) คือ data structure ที่ออกแบบมาเพื่อตอบคำถามเดียวให้เร็วที่สุด นั่นคือ ตอนนี้ตัว minimum (น้อยสุด) หรือ maximum (มากสุด) คือตัวไหน แล้ว pop (หยิบออก) มันไป โจทย์จำนวนมากบน LeetCode ที่ต้องคอยเลือกค่าสุดขั้วซ้ำ ๆ เช่น หา Kth largest (ค่ามากอันดับ k), จ้างคนที่ถูกที่สุด, หรือ process ตาม priority (ลำดับความสำคัญ) จะแก้ได้สวยงามด้วย heap

heap คืออะไร ทำไมถึงเร็ว

ลองนึกภาพว่าเรามีตัวเลขกองหนึ่ง แล้วต้อง pop ตัว minimum ออกไปเรื่อย ๆ ถ้าเราเก็บเป็น array (ลิสต์) ธรรมดา ทุกครั้งที่จะหาตัว minimum ต้อง iterate (วน) ดูทั้ง array เป็น O(n) และถ้าจะ sort (เรียง) ก่อนก็ O(n log n) แต่ heap ทำให้เรา pop ตัว minimum ออกได้ที่ O(log n) และ peek (แอบดูโดยไม่หยิบออก) ตัว minimum ได้ที่ O(1) นี่คือเหตุผลที่มันเร็วกว่ามากเมื่อต้องทำซ้ำหลายรอบ

หน้าตาของ heap คือ binary tree (ต้นไม้สองแขนง) ที่ทุก node (โหนด) ต้อง น้อยกว่าหรือเท่ากับ child (ลูก) ของมันเสมอ (สำหรับ min-heap) ผลก็คือตัว minimum จะลอยขึ้นมาอยู่บนสุด (root/ราก) เสมอ ต้นไม้นี้ store (เก็บ) ใน array แบบแนวราบ ไม่ต้องมี pointer (ตัวชี้) จริง ๆ

           1          <- ราก = ตัวน้อยสุดเสมอ
         /   \
        3     2
       / \   /
      7   4 5

# เก็บในอาร์เรย์: [1, 3, 2, 7, 4, 5]
# ลูกของ index i อยู่ที่ 2*i+1 และ 2*i+2

module heapq ใน Python

ใน Python เราไม่ต้องเขียน heap เองจากศูนย์ มี module ชื่อ heapq ในไลบรารีมาตรฐาน ที่ทำงานบน array ธรรมดาโดยตรง (มันมอง array ตัวนั้นเป็น min-heap) operation หลักมีดังนี้:

import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(h[0])            # 1  (แอบดูตัวน้อยสุด O(1))
print(heapq.heappop(h))  # 1  (หยิบตัวน้อยสุดออก)
print(heapq.heappop(h))  # 3

# แปลงลิสต์ที่มีอยู่แล้วให้เป็น heap ทันที (เร็วกว่า push ทีละตัว)
nums = [9, 4, 7, 1, 2]
heapq.heapify(nums)    # O(n)
print(heapq.heappop(nums))  # 1

อยากได้ max-heap ต้องใช้ค่าลบ

import heapq

# จำลอง max-heap ด้วยการเก็บค่าติดลบ
max_heap = []
for x in [5, 1, 8, 3]:
    heapq.heappush(max_heap, -x)   # ใส่ค่าลบ

biggest = -heapq.heappop(max_heap)  # หยิบออกแล้วใส่ลบกลับ
print(biggest)   # 8

นอกจากนี้ heapq ยังมีฟังก์ชันสำเร็จรูป nlargest และ nsmallest ที่ return k ตัวที่มาก/น้อยที่สุดจาก iterable ได้ทันที เหมาะเวลาต้องการ top-k แบบง่าย ๆ

import heapq

nums = [4, 10, 1, 7, 3, 9]
print(heapq.nlargest(3, nums))   # [10, 9, 7]  (3 ตัวมากสุด)
print(heapq.nsmallest(2, nums))  # [1, 3]      (2 ตัวน้อยสุด)

# ใช้ key ได้ด้วย เหมือน sorted
words = ["apple", "kiwi", "banana"]
print(heapq.nlargest(1, words, key=len))  # ['banana']