2.38. คิวลำดับความสำคัญ

คิวลำดับความสำคัญคือคอนเทนเนอร์ที่รู้เสมอว่ารายการใดในนั้นเล็กที่สุด (หรือใหญ่ที่สุด) โดยไม่ต้องเรียงลำดับทั้งหมด heapq นำสิ่งนี้มาใช้งานใน MicroPython โดยใช้ list ธรรมดาเป็นพื้นที่จัดเก็บและใช้อัลกอริทึมที่อิงจากโครงสร้างต้นไม้ที่เรียกว่า min-heap เพื่อคงรายการที่เล็กที่สุดไว้ที่ดัชนี 0

2.38.1. แบบจำลองทางความคิด

min-heap คือลิสต์ที่จัดเรียงให้รายการในทุกดัชนีมีค่าน้อยกว่าหรือเท่ากับรายการที่ดัชนี 2*i + 1 และ 2*i + 2 การจัดเรียงแบบนี้ทำให้การดำเนินการสามอย่างมีต้นทุนต่ำ:

• การหารายการที่เล็กที่สุด -- อยู่ที่ heap[0] เป็นการค้นหาด้วยดัชนีเพียงครั้งเดียวโดยไม่ต้องสแกน

• การเพิ่มรายการ -- รายการจะ bubble up ผ่านต้นไม้โดยเปรียบเทียบกับ parent หนึ่งโหนดต่อระดับ หนึ่งพันรายการใช้การเปรียบเทียบประมาณสิบครั้ง ส่วนหนึ่งล้านรายการใช้ประมาณยี่สิบครั้ง

• การลบรายการที่เล็กที่สุด -- เดินย้อนทางเดิมโดยใช้การเปรียบเทียบจำนวนเล็กน้อยเท่ากัน

ลิสต์นี้ ไม่ได้ ถูกเรียงลำดับ การวนซ้ำผ่านลิสต์จะให้รายการในลำดับที่ไม่แน่นอน มีเพียง heap[0] เท่านั้นที่รับประกันว่าเป็นค่าต่ำสุด

2.38.2. ฟังก์ชันสามตัวใน MicroPython

โมดูล heapq ของ MicroPython เปิดเผยฟังก์ชันเพียงสามตัว:

• heapq.heappush() -- แทรกรายการโดยรักษา heap invariant ไว้

• heapq.heappop() -- ลบและคืนค่ารายการที่เล็กที่สุด

• heapq.heapify() -- จัดเรียงลิสต์ที่มีอยู่เป็น heap ในตำแหน่งเดิม

นั่นคือขอบเขตทั้งหมด ฟังก์ชัน heappushpop, heapreplace, nlargest, nsmallest, และ merge ของ CPython ไม่มี ใน MicroPython แบบแผนด้านล่างแสดงวิธีสร้างฟังก์ชันที่ใช้บ่อยด้วยตนเอง

เริ่มต้นใหม่:

>>> import heapq
>>> heap = []
>>> heapq.heappush(heap, 5)
>>> heapq.heappush(heap, 1)
>>> heapq.heappush(heap, 3)
>>> heap
[1, 5, 3]
>>> heapq.heappop(heap)
1
>>> heapq.heappop(heap)
3
>>> heapq.heappop(heap)
5

เริ่มต้นจากข้อมูลที่มีอยู่:

>>> samples = [5, 1, 3, 2, 4]
>>> heapq.heapify(samples)
>>> samples
[1, 2, 3, 5, 4]
>>> heapq.heappop(samples)
1

การทำ Heapify จะสัมผัสแต่ละรายการหนึ่งครั้งและเร็วกว่าการ push รายการทีละตัวอย่างเห็นได้ชัด

2.38.3. Top-N จากสตรีม

การใช้งานคิวลำดับความสำคัญที่เป็นธรรมชาติ: ติดตาม N รายการที่ใหญ่ที่สุดในสตรีมที่อ่านได้เพียงครั้งเดียว

เทคนิคคือการเก็บ min-heap ขนาด N ค่าใหม่ทุกค่าจะถูก push เข้า ถ้า heap เติบโตเกิน N ให้ตัดรายการที่เล็กที่สุดทิ้ง รายการที่เล็กที่สุดอยู่ที่ heap[0] เสมอ ดังนั้นการเปรียบเทียบครั้งเดียวตัดสินว่าจะเก็บหรือทิ้งแต่ละรายการที่เข้ามา:

def top_n_brightest(readings, n):
    heap = []
    for r in readings:
        if len(heap) < n:
            heapq.heappush(heap, r)
        elif r > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, r)
    return sorted(heap, reverse=True)

heap ไม่เติบโตเกิน N ดังนั้นค่าที่เข้ามาแต่ละค่าใช้การเปรียบเทียบจำนวนเล็กน้อยเท่ากันไม่ว่าสตรีมจะยาวแค่ไหน sorted ท้ายสุดเป็นขั้นตอนเดียวที่ต้นทุนขึ้นกับ N โดยตรง

2.38.4. เหตุการณ์ที่กำหนดเวลา

คิวลำดับความสำคัญของ tuple แบบ (deadline, payload) คือรูปแบบมาตรฐานสำหรับตัวกำหนดตารางเหตุการณ์ Tuple เปรียบเทียบแบบ lexicographic ดังนั้น tuple ที่มี deadline น้อยที่สุดจะลอยขึ้นสู่จุดบนสุดโดยอัตโนมัติ:

import heapq
import time

queue = []
heapq.heappush(queue, (time.time() + 5, 'check sensors'))
heapq.heappush(queue, (time.time() + 1, 'blink LED'))
heapq.heappush(queue, (time.time() + 3, 'send heartbeat'))

while queue:
    deadline, task = queue[0]
    now = time.time()
    if now < deadline:
        time.sleep(deadline - now)
    heapq.heappop(queue)
    run(task)

ถ้าเหตุการณ์สองตัวมี deadline เดียวกัน การเปรียบเทียบ tuple จะผ่านไปยังองค์ประกอบที่สอง สำหรับ payload ที่ไม่สามารถเปรียบเทียบได้โดยธรรมชาติ ให้เพิ่มตัวนับเป็นองค์ประกอบที่สองของ tuple เพื่อบังคับลำดับที่เสถียร:

counter = 0
def schedule(deadline, task):
    global counter
    counter += 1
    heapq.heappush(queue, (deadline, counter, task))

ตอนนี้พฤติกรรม smallest-deadline-first ยังคงอยู่ การเสมอกันแก้ไขด้วยตัวนับเพื่อให้งานที่กำหนดตารางไว้ก่อนทำงานก่อน และ task ไม่จำเป็นต้องเปรียบเทียบได้

2.38.5. สิ่งที่ heapq ไม่มีให้

รูปแบบบางอย่างที่ดูเหมือนว่าควรทำงานได้ แต่ไม่ได้:

• การวนซ้ำ for x in heap ไม่ ให้ผลลัพธ์ที่เรียงลำดับ -- ลำดับพื้นฐานของลิสต์คือรูปแบบโครงสร้างต้นไม้ของ heap เพื่อใช้ heap ตามลำดับ ให้ heappop จนว่างเปล่า

• ไม่มีวิธี เปลี่ยน ลำดับความสำคัญของรายการที่อยู่ใน heap แล้ว วิธีแก้ปัญหามาตรฐานคือการ push ลำดับความสำคัญใหม่เป็นรายการใหม่และทำเครื่องหมายรายการเก่าว่าถูกยกเลิก (ข้ามไปเมื่อมัน pop ออกมา)

• heap เก็บการอ้างอิงถึงรายการ ไม่ใช่สำเนา การเปลี่ยนแปลงรายการหลังจาก push แล้วอาจทำให้ heap invariant เสีย ใช้ค่าที่ไม่เปลี่ยนแปลง (ตัวเลข, tuple) เป็นคีย์สำหรับการเปรียบเทียบ

min-heap บน plain list คือเครื่องมือที่เหมาะสมสำหรับคำถาม "อะไรเล็กที่สุด" หรือ "อะไรเร่งด่วนที่สุด" บนอุปกรณ์ embedded ขนาดเล็ก สามฟังก์ชัน หนึ่งลิสต์ และ heap จัดการส่วนที่เหลือ