Hàng đợi ưu tiên (Priority Queue) trong Python: Hướng dẫn chi tiết

Hàng đợi ưu tiên (Priority Queue) trong Python: Hướng dẫn chi tiết

Hàng đợi ưu tiên trong Python lưu trữ dữ liệu theo một thứ tự cụ thể. Có hai cách chính để triển khai hàng đợi ưu tiên: sử dụng lớp queue.PriorityQueue và module heapq.

Bạn có thể muốn sắp xếp dữ liệu dựa trên giá trị của từng mục trong danh sách. Ví dụ: bạn muốn giá trị lớn nhất xuất hiện đầu tiên và giá trị nhỏ nhất xuất hiện cuối cùng.

Đó chính là lúc hàng đợi ưu tiên phát huy tác dụng. Hàng đợi ưu tiên là một cấu trúc dữ liệu lưu trữ dữ liệu dựa trên giá trị khóa theo thứ tự tăng dần. Điều này cho phép bạn dễ dàng truy cập giá trị nhỏ nhất và lớn nhất trong hàng đợi.

Hướng dẫn này sẽ thảo luận tại sao không nên dùng list để tạo hàng đợi ưu tiên, và giới thiệu hai cách hiệu quả hơn để tạo hàng đợi ưu tiên trong Python.

Hàng đợi ưu tiên trong Python là gì?

Hàng đợi ưu tiên là phiên bản cải tiến của hàng đợi (queue) thông thường, lưu trữ dữ liệu theo thứ tự ưu tiên của từng phần tử. Mức ưu tiên của mỗi phần tử được quyết định dựa trên giá trị của chính phần tử đó.

Trong khoa học máy tính, hàng đợi (queue) là cấu trúc dữ liệu lưu trữ các mục theo thứ tự先进先出 (FIFO - First In, First Out). Có một số tình huống việc sử dụng cấu trúc này rất hữu ích.

Ví dụ, giả sử bạn đang xây dựng ứng dụng theo dõi đơn hàng cho một nhà hàng. Người đặt món đầu tiên nên được phục vụ trước những người đặt sau. Để theo dõi đơn hàng, bạn nên dùng hàng đợi.

Có hai cách để định nghĩa hàng đợi ưu tiên trong Python:

• Sử dụng lớp queue.PriorityQueue
• Sử dụng module heapq

Bạn có thể định nghĩa hàng đợi ưu tiên bằng cấu trúc list. Tuy nhiên, chiến lược này kém hiệu quả hơn so với việc dùng queue.PriorityQueue hoặc module heapq.

Hàng đợi ưu tiên Python: queue.PriorityQueue

Lớp queue.PriorityQueue tạo ra một hàng đợi ưu tiên trong Python. Lớp này là một phần của thư viện queue chuẩn của Python. Bạn cần import thư viện queue để sử dụng lớp này. Để lấy một mục từ PriorityQueue, bạn có thể dùng phương thức get().

Để truy cập lớp PriorityQueue, ta cần import nó vào mã nguồn:

from queue import PriorityQueue

Giả sử ta muốn tạo hàng đợi ưu tiên cho các người giữ vé tại một buổi hòa nhạc địa phương. Ta có thể làm như sau:

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)

Kết quả trả về:

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

Trong mã trên, ta trước tiên import lớp PriorityQueue từ thư viện queue, sau đó khởi tạo hàng đợi ưu tiên tên ticket_holders. Tiếp theo, ta chèn ba tuple vào hàng đợi, mỗi tuple lưu số vé và tên người giữ vé.

Ta dùng vòng lặp while để duyệt qua từng mục trong hàng đợi ticket_holders, sau đó lấy mục đó bằng phương thức get().

Phương thức queue.PriorityQueue hiệu quả và dễ sử dụng, là lựa chọn tuyệt vời khi bạn cần tạo hàng đợi ưu tiên.

Hàng đợi ưu tiên Python: Module heapq

Module heapq cho phép bạn định nghĩa hàng đợi ưu tiên trong Python. Cấu trúc dữ liệu heapq loại bỏ các mục theo thứ tự ưu tiên. Giá trị nhỏ nhất có ưu tiên thấp nhất, giá trị lớn nhất có ưu tiên cao nhất trong cấu trúc heapq.

Trước khi dùng heapq, ta phải import module này:

import heapq

Quay lại ví dụ trước. Giả sử ta muốn tạo hàng đợi ưu tiên lưu thông tin người giữ vé tại buổi hòa nhạc. Ta có thể làm như sau:

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)

Kết quả trả về:

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

Đầu tiên, ta import thư viện heapq, sau đó khởi tạo biến ticket_holders là một list rỗng. Ta dùng phương thức heappush() để đẩy ba tuple vào hàng đợi ưu tiên. Hàng đợi này lưu số vé và tên của từng người giữ vé.

Sau đó, ta tạo vòng lặp while duyệt qua từng mục trong hàng đợi. Vòng lặp loại bỏ mục ở đỉnh hàng đợi bằng heappop(), sau đó in mục đó ra màn hình. Như bạn thấy, tất cả các mục đều được in theo thứ tự ưu tiên.

Tại sao không nên dùng List

Về mặt kỹ thuật, bạn có thể tạo hàng đợi ưu tiên bằng cấu trúc dữ liệu list của Python. Cách làm là tạo một list, sau đó sắp xếp nó theo thứ tự tăng dần.

Tuy nhiên, đây là cách tương đối kém hiệu quả để duy trì hàng đợi ưu tiên. Khi bạn thay đổi các mục trong list, bạn cần sắp xếp lại list, điều này tốn thời gian.

Bạn có thể dùng list truyền thống làm hàng đợi ưu tiên nếu chỉ cần lưu vài giá trị. Nhưng nếu muốn tạo hàng đợi lớn hơn, list không phải lựa chọn tốt.

Để tham khảo, hãy xem ví dụ hàng đợi ưu tiên dùng list. Giả sử ta muốn tạo hàng đợi ưu tiên lưu thứ tự người giữ vé được vào buổi hòa nhạc đầu tiên:

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)

Kết quả trả về:

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

Ta tạo list ticket_holders, thêm ba tuple vào. Mỗi tuple chứa số vé và tên người giữ vé. Sau đó, ta dùng hàm sort() của Python để sắp xếp list theo thứ tự ngược.

Ta tạo vòng lặp while duyệt qua từng mục trong list ticket_holders và lấy mục ở đỉnh list. Mã in mục vừa loại bỏ ra màn hình.

Kết luận

Hai cách phổ biến nhất để tạo hàng đợi ưu tiên là dùng module heapq hoặc lớp queue.PriorityQueue. Mặc dù về mặt kỹ thuật bạn có thể dùng list làm hàng đợi ưu tiên, cách này không mở rộng tốt.

Hướng dẫn này đã thảo luận, kèm ví dụ, cách tạo hàng đợi ưu tiên trong Python. Bây giờ bạn đã trang bị kiến thức cần thiết để bắt đầu tạo hàng đợi ưu tiên của riêng mình như một chuyên gia Python!

Để có thêm hướng dẫn về cách học Python, hãy xem hướng dẫn hoàn chỉnh "Cách học Python" của chúng tôi.