คิวความสำคัญ (Priority Queue) ใน Python: คู่มือฉบับสมบูรณ์

คิวความสำคัญ (Priority Queue) ใน Python: คู่มือฉบับสมบูรณ์

คิวความสำคัญใน Python จัดเก็บข้อมูลตามลำดับความสำคัญ มีสองวิธีหลักในการนำไปใช้: ใช้คลาส queue.PriorityQueue และโมดูล heapq

คุณอาจต้องการจัดลำดับข้อมูลตามค่าของแต่ละรายการในลิสต์ เช่น ต้องการให้ค่าสูงสุดอยู่หน้าสุด และค่าต่ำสุดอยู่ท้ายสุด ซึ่งก็คือที่มาของคิวความสำคัญ (Priority Queue)

คิวความสำคัญเป็นโครงสร้างข้อมูลที่จัดเก็บข้อมูลตามค่าของคีย์ (key) ในลำดับน้อยไปมาก (ascending order) ทำให้เข้าถึงค่าที่น้อยที่สุดและมากที่สุดได้อย่างง่ายดาย

บทช่วยสอนนี้จะอธิบายว่าทำไมไม่ควรใช้ลิสต์ (list) ธรรมดาในการสร้างคิวความสำคัญ และจะแนะนำสองวิธีที่มีประสิทธิภาพมากกว่า

คิวความสำคัญใน Python คืออะไร?

คิวความสำคัญเป็นรูปแบบปรับเปลี่ยนของคิว (queue) ที่จัดเก็บข้อมูลตามลำดับความสำคัญของแต่ละองค์ประกอบ ความสำคัญของแต่ละองค์ประกอบถูกกำหนดโดยค่าขององค์ประกอบนั้นเอง

ในวิทยาการคอมพิวเตอร์ คิวเป็นโครงสร้างข้อมูลที่จัดเก็บรายการตามลำดับ First-In, First-Out (FIFO) มีสถานการณ์บางอย่างที่โครงสร้างนี้มีประโยชน์

เช่น สมมติว่าคุณกำลังสร้างแอปติดตามออเดอร์สำหรับร้านอาหาร คนที่สั่งอาหารก่อนควรได้รับบริการก่อนคนที่สั่งทีหลัง เพื่อติดตามออเดอร์ คุณควรใช้คิว

มีสองวิธีในการกำหนดคิวความสำคัญใน Python:

• ใช้คลาส queue.PriorityQueue
• ใช้โมดูล heapq

คุณสามารถกำหนดคิวความสำคัญโดยใช้โครงสร้างลิสต์ได้ แต่กลยุทธ์นี้มีประสิทธิภาพน้อยกว่าการใช้ PriorityQueue หรือ heapq

คิวความสำคัญ Python: queue.PriorityQueue

คลาส queue.PriorityQueue สร้างคิวความสำคัญใน Python คลาสนี้เป็นส่วนหนึ่งของไลบรารี queue คุณต้องนำเข้าไลบรารี queue ก่อนจึงจะใช้งานได้ ในการดึงรายการจาก PriorityQueue สามารถใช้เมธอด get()

เพื่อเข้าถึงคลาส PriorityQueue เราต้องนำเข้า (import) มันเข้ามาในโค้ด ซึ่งทำได้ด้วยคำสั่ง import ดังนี้:

from queue import PriorityQueue

สมมติว่าเราต้องการสร้างคิวความสำคัญสำหรับผู้ถือบัตรคอนเสิร์ต เราสามารถทำได้ด้วยโค้ดนี้:

from queue import PriorityQueue
ticket_holders = PriorityQueue()
ticket_holders.put((3, 'Paul'))
ticket_holders.put((1, 'Miles'))
ticket_holders.put((2, 'Dani'))
while not ticket_holders.empty():
    item = ticket_holders.get()
    print(item)

โค้ดของเราคืนค่า:

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

ในโค้ด เรานำเข้า PriorityQueue จากไลบรารี queue แล้วสร้างคิวความสำคัญชื่อ ticket_holders ต่อมา เราเพิ่มทูเพิล (tuple) สามคู่เข้าไปในคิว ซึ่งแต่ละคู่เก็บหมายเลขบัตรและชื่อของผู้ถือบัตร

เราใช้ลูป while เพื่อวนผ่านทุกรายการในคิว ticket_holders จากนั้นดึงรายการนั้นๆ ด้วย get()

เมธอด queue.PriorityQueue มีประสิทธิภาพและใช้งานง่าย ทำให้เป็นตัวเลือกที่ดีเมื่อต้องสร้างคิวความสำคัญ

คิวความสำคัญ Python: โมดูล heapq

โมดูล heapq ให้คุณกำหนดคิวความสำคัญใน Python โครงสร้างข้อมูล heapq นำรายการออกตามลำดับความสำคัญ ค่าที่น้อยที่สุดมีความสำคัญต่ำสุด และค่าที่มากที่สุดมีความสำคัญสูงสุดในโครงสร้าง heapq

ก่อนใช้งาน heapq ต้องนำเข้าโมดูลก่อน:

import heapq

กลับไปที่ตัวอย่างก่อนหน้า สมมติเราต้องการสร้างคิวความสำคัญเก็บข้อมูลผู้ถือบัตรคอนเสิร์ต สามารถทำได้ด้วย heapq และโปรแกรมนี้:

import heapq
ticket_holders = []
heapq.heappush(ticket_holders, (3, 'Paul'))
heapq.heappush(ticket_holders, (1, 'Miles'))
heapq.heappush(ticket_holders, (2, 'Dani'))
while ticket_holders:
    item = heapq.heappop(ticket_holders)
    print(item)

โค้ดคืนค่า:

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

ก่อนอื่น เรานำเข้าไลบรารี heapq แล้วสร้างตัวแปร ticket_holders เป็นลิสต์ว่าง ใช้ heappush() เพื่อเพิ่มทูเพิลสามคู่เข้าไปในคิวความสำคัญ คิวนี้เก็บหมายเลขบัตรและชื่อของผู้ถือบัตร

จากนั้นสร้างลูป while วนผ่านทุกรายการในคิว ลูปนำรายการที่อยู่บนสุดออกด้วย heappop() แล้วพิมพ์รายการที่ถูกนำออกไปที่คอนโซล มองเห็นได้ว่ารายการทั้งหมดถูกพิมพ์ตามลำดับความสำคัญ

ทำไมไม่ควรใช้ลิสต์ (List) ธรรมดา

ทางเทคนิค คุณสามารถสร้างคิวความสำคัญด้วยโครงสร้างข้อมูลลิสต์ของ Python ได้ โดยสร้างลิสต์แล้วจัดเรียงในลำดับน้อยไปมาก

อย่างไรก็ตาม วิธีนี้มีประสิทธิภาพค่อนข้างต่ำในการดูแลรักษาคิวความสำคัญ เนื่องจากเมื่อคุณเปลี่ยนแปลงรายการในลิสต์ คุณต้องจัดเรียงลิสต์ใหม่ ซึ่งใช้เวลา

คุณอาจใช้ลิสต์ธรรมดาเป็นคิวความสำคัญได้ หากเพียงต้องจัดเก็บค่าน้อยๆ แต่หากต้องการสร้างคิวขนาดใหญ่ ลิสต์ไม่ใช่ตัวเลือกที่ดี

เพื่อการอ้างอิง มาดูตัวอย่างคิวความสำคัญด้วยลิสต์ สมมติเราต้องการสร้างคิวเก็บลำดับผู้ถือบัตรที่ควรเข้าคอนเสิร์ตก่อน ใช้โค้ดนี้:

ticket_holders = []
ticket_holders.append((3, 'Paul'))
ticket_holders.append((1, 'Miles'))
ticket_holders.append((2, 'Dani'))
ticket_holders.sort(reverse=True)
while ticket_holders:
    item = ticket_holders.pop()
    print(item)

โค้ดคืนค่า:

(1, 'Miles')
(2, 'Dani')
(3, 'Paul')

เราสร้างลิสต์ ticket_holders เพิ่มทูเพิลสามคู่ แต่ละคู่มีหมายเลขบัตรและชื่อ จากนั้นใช้ฟังก์ชัน sort() จัดเรียงลิสต์ในลำดับย้อนกลับ (reverse)

สร้างลูป while วนผ่านทุกรายการในลิสต์ และนำรายการบนสุดออกด้วย pop() แล้วพิมพ์รายการที่ถูกนำออก

สรุป

สองวิธีที่พบบ่อยที่สุดในการสร้างคิวความสำคัญคือใช้โมดูล heapq หรือคลาส queue.PriorityQueue แม้จะสามารถใช้ลิสต์ได้ แต่วิธีนี้ไม่รองรับการขยายขนาด (scale) ได้ดี

บทช่วยสอนนี้อธิบายพร้อมตัวอย่างวิธีสร้างคิวความสำคัญใน Python ตอนนี้คุณพร้อมที่จะสร้างคิวความสำคัญของตัวเองได้แล้วอย่างมืออาชีพ!

สำหรับคำแนะนำเพิ่มเติมเกี่ยวกับการเรียนรู้ Python ดูคู่มือ How to Learn Python ของเรา