Heapq được triển khai như thế nào trong python?

Trong bài đăng này, chúng tôi tìm hiểu cách tạo hàng đợi ưu tiên bằng Python. Có 3 cách chính để triển khai và sử dụng hàng đợi ưu tiên trong Python

• Tạo danh sách và sắp xếp theo cách thủ công
• Sử dụng một đống nhị phân trên cơ sở mô-đun heapq của Python
• Sử dụng triển khai hàng đợi ưu tiên từ gói Queue của Python

Cách đầu tiên thực sự không được khuyến khích vì nó không hiệu quả và dễ bị lỗi. Do đó, chúng ta sẽ xem xét hai cách sau và cũng tìm hiểu cách tạo lớp hàng đợi ưu tiên của riêng mình trên cơ sở một đống

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

Hàng đợi ưu tiên mở rộng hàng đợi bằng cách liên kết các mục với mức độ ưu tiên. Các mục có mức độ ưu tiên cao hơn sẽ được xếp trước ngay cả khi chúng không ở đầu hàng. Khi hai phần tử có cùng mức độ ưu tiên, hàng đợi sẽ phục vụ chúng theo thứ tự vào trước ra trước (FIFO)

Hàng đợi ưu tiên thường hỗ trợ ít nhất ba thao tác

• cộng. thêm một mục vào cuối hàng đợi
• nhạc pop. truy xuất mục có mức ưu tiên cao nhất đầu tiên trong hàng đợi
• trống rỗng. kiểm tra xem hàng đợi có trống không

Hàng đợi ưu tiên đại diện cho cấu trúc dữ liệu trừu tượng. Cấu trúc dữ liệu trừu tượng xác định hành vi dự kiến, chẳng hạn như các mục đó phải được sắp xếp theo mức độ ưu tiên. Nhưng họ không xác định việc thực hiện. Để triển khai hàng đợi ưu tiên, bạn cần có cấu trúc dữ liệu cụ thể, chẳng hạn như một đống nhị phân. Trong Python, một cách phổ biến để triển khai hàng đợi ưu tiên là mô-đun heapq

Đống là gì?

Một đống thực hiện một cấu trúc cây nhị phân. Cây nhị phân bao gồm một hệ thống phân cấp các nút trong đó mỗi nút cha luôn có hai nút con. Trong một đống tối đa, nút có giá trị lớn nhất nằm trên cùng. Trong một đống tối thiểu, nút có giá trị nhỏ nhất nằm trên cùng

Bất cứ khi nào bạn thêm một nút mới có giá trị nhỏ hơn các nút lớn nhất, nó sẽ thấm lên vị trí của nó trong cây trong khi các giá trị lớn hơn sẽ thấm xuống. Ví dụ: nếu chúng ta thêm 1 vào một đống tối thiểu với 2 ở trên cùng, một đống sẽ tăng lên

Sau khi quá trình sắp xếp lại kết thúc, cái cây sẽ như thế này

Lưu ý rằng các nút ở cùng cấp độ không cần phải sắp xếp theo thứ tự tăng dần nghiêm ngặt. Ví dụ: nếu 5 và 6 được hoán đổi, thuộc tính heap vẫn được duy trì

Để triển khai hàng đợi ưu tiên bằng cách sử dụng min-heap, chúng tôi sẽ chỉ định mức độ ưu tiên theo thứ tự tăng dần. Mục có giá trị thấp nhất được ưu tiên cao nhất. Bất cứ khi nào chúng ta thêm một giá trị mới, quá trình sắp xếp lại đảm bảo rằng mục mới được đặt ở vị trí tương ứng với mức độ ưu tiên của nó trong heap. Khi thăm dò các mục từ hàng đợi, chúng tôi chỉ cần lấy nút ở trên cùng của heap

Heapq trong Python

Mô-đun heapq thực hiện một cây nhị phân hoàn chỉnh. Nếu chúng ta có một danh sách các phần tử không có thứ tự, chúng ta có thể sử dụng mô-đun heapq để biến nó thành hàng đợi ưu tiên

l = [5, 3, 1, 8, 6, 2, 7]
heapq.heapify(l)
l #[1, 3, 2, 8, 6, 5, 7]

Tiếp theo, bạn có thể bật các mục ra khỏi hàng ưu tiên, việc này sẽ sắp xếp lại thứ tự đống để mục có mức ưu tiên cao nhất tiếp theo sẽ xếp hàng tiếp theo

heapq.heappop(l) # 1
print(l) # [2, 3, 5, 8, 6, 7]

heapq.heappop(l) # 2
print(l) # [3, 6, 5, 8, 7]

Nếu bạn đẩy một mục vào hàng đợi, nó sẽ được đặt ở vị trí thích hợp trong đống

heapq.heappush(l, 9)
print(l) # [3, 6, 5, 8, 7, 9]

heapq.heappush(l, 4)
print(l) # [3, 6, 4, 8, 7, 9, 5]

Ngoài pop và push, mô-đun heapq còn có chức năng heapreplace, bật một mục và ngay lập tức đẩy một mục mới vào heap

l = [5, 3, 1, 8, 6, 2, 7]
heapq.heapify(l)
print(l) #[1, 3, 2, 8, 6, 5, 7]
heapq.heapreplace(l, 4)
print(l) #[2, 3, 4, 8, 6, 5, 7]

Heappushpop đảo ngược thứ tự hoạt động của heapreplace bằng cách đẩy trước và bật lên tiếp theo

l = [5, 3, 1, 8, 6, 2, 7]
heapq.heapify(l)
print(l) #[1, 3, 2, 8, 6, 5, 7]
heapq.heappushpop(l, 4)
print(l) #[2, 3, 4, 8, 6, 5, 7]

Hai phương pháp này thường hiệu quả hơn trong trường hợp bạn cần thực hiện lần đẩy và bật liên tiếp hoặc ngược lại

Hàng đợi ưu tiên tùy chỉnh dựa trên Heapq

Trong ví dụ trên, chúng tôi đã sử dụng mô-đun heap để biến danh sách thành hàng đợi ưu tiên. Chúng tôi phải thao tác rõ ràng với danh sách bằng cách sử dụng các hàm từ mô-đun heap. Điều này dễ xảy ra lỗi vì chúng ta vẫn có thể tương tác với danh sách thông qua giao diện danh sách, điều này có thể làm xáo trộn hàng đợi ưu tiên của chúng ta. Hãy tưởng tượng chúng ta tạo một hàng đợi ưu tiên và sau đó ai đó nối thêm một phần tử bằng chức năng nối thêm tiêu chuẩn của danh sách

l = [5, 3, 8, 6, 2, 7]
heapq.heapify(l)
print(l) #[2, 3, 7, 6, 5, 8]
l.append(1)
print(l) #[2, 3, 7, 6, 5, 8, 1]

Số 1 hiện ở cuối hàng đợi thay vì ở đầu

Để tránh vấn đề này, chúng ta có thể tạo một lớp trình bao bọc tùy chỉnh xung quanh danh sách sử dụng heap

class PriorityQueue:
    def __init__(self, elements = None):
      if(elements == None):
        self.elements = list()
      elif type(elements) == list:
        heapq.heapify(elements)
        self.elements = elements
        
    def __str__(self):
        return str(self.elements)
  
    # for checking if the queue is empty
    def isEmpty(self):
        return len(self.elements) == 0
  
    # for inserting an element in the queue
    def push(self, element):
        heapq.heappush(self.elements, element)

    # for popping an element based on Priority
    def pop(self):
        heapq.heappop(self.elements)

Hàm tạo của lớp hàng đợi ưu tiên lấy một danh sách tùy chọn với các giá trị ban đầu làm đối số. Nếu có một danh sách các giá trị ban đầu, chúng ta gộp nó lại để tạo thứ tự cho hàng đợi ưu tiên rồi gán nó cho biến đối tượng có tên là phần tử

#creating an empty priority queue
q = PriorityQueue()

#creating a priority queue with initial values
q = PriorityQueue([5, 3, 1, 8, 6, 2, 7])
print(q) [1, 3, 2, 8, 6, 5, 7]#

Bây giờ chúng ta có thể áp dụng các thao tác đẩy và bật. Hàng đợi luôn đảm bảo rằng giá trị thấp nhất (có mức ưu tiên cao nhất) ở phía trước

q = PriorityQueue()
q.push(5)
q.push(4)
q.push(1)
q.push(2)
q.push(5)

print(q) #[1, 2, 4, 5, 5]

q.pop()
print(q) #[2, 5, 4, 5]
q.pop()
print(q) #[4, 5, 5]

Cuối cùng, chúng ta cũng có thể kiểm tra xem hàng đợi có trống không

q = PriorityQueue()
print(q.isEmpty()) #True

q = PriorityQueue([5, 3, 1, 8, 6, 2, 7])
print(q.isEmpty()) #False

Hàng đợi ưu tiên Python sử dụng Mô-đun hàng đợi

Cuối cùng nhưng không kém phần quan trọng, Python cung cấp cho chúng ta triển khai hàng đợi ưu tiên sẵn sàng trong mô-đun hàng đợi của họ

Hàng đợi ưu tiên Python từ mô-đun hàng đợi dựa trên một đống nhị phân từ mô-đun heapq. Trái với cách triển khai trực tiếp dựa trên heapq, hàng đợi ưu tiên Python đảm bảo an toàn cho luồng. Do đó, việc triển khai này thích hợp hơn trong môi trường đa luồng

Giao diện hơi khác một chút. Thay vì push bạn dùng put và thay vì pop bạn dùng get

heapq.heappop(l) # 1
print(l) # [2, 3, 5, 8, 6, 7]

heapq.heappop(l) # 2
print(l) # [3, 6, 5, 8, 7]

Như bạn có thể thấy, thứ tự của các mục giống như trong triển khai tùy chỉnh của chúng tôi. Nhưng bạn không thể chuyển một mảng giá trị ban đầu.

Chỉnh sửa. Như Luke van Hulle đã chỉ ra một cách hữu ích trong các nhận xét, bạn cũng có thể in toàn bộ hàng đợi như sau

heapq.heappop(l) # 1
print(l) # [2, 3, 5, 8, 6, 7]

heapq.heappop(l) # 2
print(l) # [3, 6, 5, 8, 7]

Mặt khác, bạn phải bật từng mục từ danh sách như đã trình bày ở trên bằng phương thức get

Bạn cũng nên kiểm tra xem hàng đợi có trống không trước khi cố truy xuất một mục. Nếu không có mục nào trong hàng đợi, hàm get sẽ không kết thúc. Rốt cuộc, một mục có thể đến từ một chủ đề khác. Trong môi trường một luồng, đây không phải là vấn đề vì không có mục nào có thể đến miễn là hàm get đang chạy và do đó đang chiếm luồng khả dụng duy nhất

Python Heapq hoạt động như thế nào?

Làm cách nào để cài đặt heapq trong Python?

Làm cách nào để triển khai hàng đợi ưu tiên bằng heap trong Python?

Heapq có phải là thư viện Python chuẩn không?