Heap queue (hàng đợi heap) hoặc heapq trong Python

Category: Python

Heap queue hay còn gọi là priority queue (hàng đợi ưu tiên) là một cấu trúc dữ liệu cho phép chúng ta truy cập nhanh đến phần tử nhỏ nhất (với min-heap) hoặc lớn nhất (với max-heap). Heap thường được triển khai dưới dạng cây nhị phân, trong đó giá trị của mỗi nút cha nhỏ hơn (đối với min-heap) hoặc lớn hơn (đối với max-heap) các nút con của nó.

Tuy nhiên, trong Python, heap thường được triển khai dưới dạng min-heap, có nghĩa là phần tử nhỏ nhất luôn nằm ở gốc của cây, giúp việc truy cập trở nên dễ dàng hơn.

Mô-đun heapq cho phép chúng ta xử lý một danh sách như một heap, cung cấp các phương thức hiệu quả để thêm và xóa phần tử.

Tạo một Heap Queue

Để sử dụng heap queue trong Python, trước tiên chúng ta cần import mô-đun heapq .
Một heap queue được tạo từ một danh sách bằng cách gọi hàm heapq.heapify(), hàm này sẽ sắp xếp lại các phần tử trong danh sách để tạo thành một cấu trúc heap hợp lệ.

import heapq

# Tạo danh sách
li = [10, 20, 15, 30, 40]

# Chuyển đổi danh sách thành một đống
heapq.heapify(li)

print("Heap queue:", li)

Đầu ra:

Heap queue: [10, 20, 15, 30, 40]

Giải thích:

  • heapq.heapify(li) sắp xếp lại các phần tử của danh sách thành một heap hợp lệ tại chỗ.

  • Danh sách đầu ra biểu diễn cấu trúc heap và phần tử đầu tiên của nó luôn là phần tử nhỏ nhất (trong min-heap).

Các hoạt động chính của heap :

  • Đẩy (heappush) : Thêm một phần tử vào heap trong khi vẫn duy trì thuộc tính của heap.

  • Pop (heappop) : Xóa và trả về phần tử nhỏ nhất trong heap, vẫn duy trì thuộc tính heap.

  • Peek : Xem phần tử nhỏ nhất mà không xóa nó.

  • Heapify : Chuyển đổi một danh sách thông thường thành một heap hợp lệ tại chỗ.

Thêm và Popping các phần tử từ một hàng đợi Heap

Hàng đợi heap cho phép chúng ta thêm phần tử và xóa phần tử nhỏ nhất một cách hiệu quả. Hàm heappush() được sử dụng để thêm phần tử vào heap trong khi vẫn duy trì thuộc tính heap và heappop() được sử dụng để xóa phần tử nhỏ nhất. Để thêm và xóa phần tử khỏi hàng đợi heap, chúng ta có thể sử dụng hai hàm sau:

  • Hàm heapq.heappush() thêm một phần tử mới vào heap trong khi vẫn duy trì thứ tự của heap.

  • Hàm heapq.heappop() xóa phần tử nhỏ nhất khỏi heap và trả về phần tử đó.

Ví dụ:

import heapq

# Tạo một đống ban đầu
h = [10, 20, 15, 30, 40]
heapq.heapify(h)

# Thêm một phần tử
heapq.heappush(h, 5)

# Lấy phần tử nhỏ nhất ra khỏi đống
min = heapq.heappop(h)

print(h)

print("Smallest:", min)
print(h)

Đầu ra:

[10, 20, 15, 30, 40]
Smallest: 5
[10, 20, 15, 30, 40]

Giải thích:

  • Phần tử thứ 5 được đẩy vào heap và sau khi thực hiện thao tác, nó được đặt ở gốc vì nó là phần tử nhỏ nhất.

  • Hàm heappop() xóa phần tử nhỏ nhất (5) khỏi heap và trả về phần tử đó.

  • Sau khi bật ra, phần tử nhỏ nhất tiếp theo (10) sẽ trở thành gốc.

Thêm và Bật đồng thời

Mô-đun heapq của Python cung cấp một cách hiệu quả để thực hiện việc này bằng cách sử dụng hàm heappushpop() . Hàm này cho phép chúng ta đẩy một phần tử vào heap và pop phần tử nhỏ nhất trong một thao tác kết hợp. Nó nhanh hơn so với việc thực hiện các thao tác này riêng lẻ, vì nó duy trì thuộc tính heap trong một lần.

hàm heappuspop() có hai đối số:

  • Một đống (danh sách).

  • Một phần tử để đẩy vào đống.

Ví dụ về việc thêm và bật ra cùng lúc:

import heapq

# Tạo một đống
h = [10, 20, 15, 30, 40]
heapq.heapify(h)

# Đẩy một phần tử mới (5) và loại bỏ phần tử nhỏ nhất cùng lúc
min = heapq.heappushpop(h, 5)

print(min)
print(h)

Đầu ra:

5 
[10, 20, 15, 30, 40]

Giải thích:

  • Phần tử 5 được thêm vào heap bằng cách sử dụng heappush().

  • Sau đó, heappop() được sử dụng để loại bỏ phần tử nhỏ nhất (5) vừa được thêm vào.

Tìm phần tử lớn nhất và nhỏ nhất trong hàng đợi Heap

Mặc dù heap cho phép truy cập hiệu quả vào phần tử nhỏ nhất, nhưng nó không hỗ trợ trực tiếp việc tìm phần tử lớn nhất. Tuy nhiên, mô-đun heapq cung cấp hai hàm tiện dụng, nlargest() và nsmallest() , để truy xuất phần tử lớn nhất và nhỏ nhất từ ​​heap.

nlargest() và nsmallest()

Các hàm này cho phép chúng ta dễ dàng tìm thấy n phần tử lớn nhất hoặc n phần tử nhỏ nhất trong một đống. Chúng thực hiện điều này bằng cách quét đống một cách hiệu quả và sắp xếp số lượng phần tử cần thiết.

  • heapq.nlargest(n, iterable) trả về n phần tử lớn nhất từ ​​iterable.

  • heapq.nsmallest(n, iterable) trả về n phần tử nhỏ nhất từ ​​iterable.

Ví dụ về cách tìm phần tử lớn nhất và nhỏ nhất bằng cách sử dụng nlargest() và nsmallest():

import heapq

# tạo 1 heap
h = [10, 20, 15, 30, 40]
heapq.heapify(h)

# Tìm 3 phần tử lớn nhất 
max = heapq.nlargest(3, h)
print("3 largest elements:", maxi)

# Tìm 3 phần tử nhỏ nhất
min = heapq.nsmallest(3, h)
print("3 smallest elements:", min)

Đầu ra

3 largest elements: [40, 30, 20] 
3 smallest elements: [10, 15, 20]

Lưu ý rằng mô-đun heapq trong Python cung cấp các hàm để thực hiện các hoạt động heap trên danh sách tại chỗ, mà không cần tạo cấu trúc dữ liệu riêng cho heap. Mô-đun heapq hiệu quả và dễ sử dụng, khiến nó trở thành lựa chọn phổ biến để triển khai hàng đợi ưu tiên và các cấu trúc dữ liệu khác trong Python.

Thay thế và hợp nhất các hoạt động trên Heapq

Mô-đun heapq của Python cung cấp các hoạt động hữu ích bổ sung cho heap như thay thế và hợp nhất.

Thay thế hoạt động

Hàm heapq.heapreplace() là sự kết hợp của pop và push. Nó sẽ đẩy phần tử nhỏ nhất ra khỏi heap và chèn một phần tử mới vào heap, duy trì thuộc tính heap. Hoạt động này hữu ích khi chúng ta muốn thay thế phần tử nhỏ nhất bằng một giá trị mới trong heap.

  • Nó trả về phần tử nhỏ nhất trước khi thay thế phần tử đó.

  • Phương pháp này hiệu quả hơn so với việc sử dụng heappop() theo sau là heappush() vì nó thực hiện cả hai thao tác trong một bước.

Hoạt động hợp nhất

Hàm heapq.merge() được sử dụng để hợp nhất nhiều iterable đã sắp xếp thành một heap đã sắp xếp duy nhất. Nó trả về một iterator qua các giá trị đã sắp xếp, sau đó chúng ta có thể lặp qua.

Hoạt động này hiệu quả vì nó tránh việc sắp xếp các phần tử từ đầu. Thay vào đó, nó hợp nhất các phần tử lặp đã được sắp xếp theo cách duy trì thuộc tính heap.

Ví dụ về các thao tác thay thế và hợp nhất:

import heapq
# Tạo 1 đống
h1 = [10, 20, 15, 30, 40]
heapq.heapify(h1)

# Thay thế phần tử nhỏ nhất (10) thành 5
min = heapq.heapreplace(h1, 5)

print(min)
print(h1)

# Hợp nhất heap
h2 = [2, 4, 6, 8]

# Sáp nhập các danh sách
h3 = list(heapq.merge(h1, h2))
print("Merged heap:", h3)

Đầu ra

10 
[5, 20, 15, 30, 40] 
Merged heap: [2, 4, 5, 6, 8, 20, 15, 30, 40]

Giải thích:

  • Chúng tôi sử dụng heapreplace() để thay thế phần tử nhỏ nhất (10) bằng 5. Phần tử nhỏ nhất được loại bỏ và 5 được chèn vào heap.

  • Chúng tôi sử dụng heapq.merge() để hợp nhất các heap này thành một heap được sắp xếp duy nhất trong khi vẫn duy trì thuộc tính heap.

Ưu điểm của việc sử dụng hàng đợi heap (hay heapq) trong Python:

  • Hiệu quả : Hàng đợi heap là một cấu trúc dữ liệu hiệu quả cao để quản lý hàng đợi ưu tiên và heap trong Python. Nó cung cấp độ phức tạp thời gian logarit cho nhiều hoạt động, khiến nó trở thành lựa chọn phổ biến cho nhiều ứng dụng.

  • Tiết kiệm không gian : Hàng đợi heap lưu trữ các phần tử theo định dạng giống danh sách. Điều này có nghĩa là chúng không chiếm thêm không gian không cần thiết, khiến chúng thân thiện với bộ nhớ hơn một số tùy chọn khác, như danh sách được liên kết.

  • Dễ sử dụng : Mô-đun heapq cung cấp các hàm dễ hiểu cho phép chúng ta nhanh chóng thêm, xóa hoặc lấy các phần tử mà không gặp nhiều rắc rối.

  • Linh hoạt : Hàng đợi heap trong Python có thể được sử dụng để triển khai nhiều cấu trúc dữ liệu khác nhau như hàng đợi ưu tiên, heap và cây nhị phân, khiến chúng trở thành một công cụ đa năng cho nhiều ứng dụng.

Nhược điểm của việc sử dụng hàng đợi heap (hay heapq) trong Python:

  • Chức năng hạn chế : Heap có thể không hoạt động tốt đối với các hoạt động phức tạp hơn hoặc các cấu trúc dữ liệu yêu cầu các tính năng khác nhau.

  • Không có quyền truy cập ngẫu nhiên : Hàng đợi heap không hỗ trợ quyền truy cập ngẫu nhiên vào các phần tử, khiến việc truy cập các phần tử ở giữa heap hoặc sửa đổi các phần tử không nằm ở đầu heap trở nên khó khăn.

  • Không sắp xếp: Hàng đợi heap không hỗ trợ sắp xếp, vì vậy nếu chúng ta cần sắp xếp các phần tử theo thứ tự cụ thể, chúng ta sẽ cần sử dụng một cấu trúc dữ liệu hoặc thuật toán khác.

  • Không an toàn cho luồng : Hàng đợi heap không được thiết kế để xử lý nhiều luồng truy cập dữ liệu cùng một lúc.

Nhìn chung, hàng đợi heap là một cấu trúc dữ liệu linh hoạt và hiệu quả cao để quản lý hàng đợi ưu tiên và heap trong Python, nhưng có thể có chức năng hạn chế và không phù hợp với mọi ứng dụng.

Published on Jun 19, 2025