Hướng dẫn priority queue of objects python - hàng đợi ưu tiên của các đối tượng python

Cấu trúc dữ liệu - Hàng đợi ưu tiên & Heapq

Tìm kiếm trang web Bogotobogo.com:

Hàng đợi ưu tiên

Hàng đợi ưu tiên là một loại dữ liệu trừu tượng (ADT) giống như một hàng đợi thông thường hoặc cấu trúc dữ liệu ngăn xếp, nhưng trong đó mỗi phần tử có mức độ ưu tiên liên quan đến nó. Trong hàng đợi ưu tiên, một yếu tố có mức độ ưu tiên cao được phục vụ trước một yếu tố có mức độ ưu tiên thấp. Nếu hai yếu tố có cùng mức độ ưu tiên, chúng được phục vụ theo đơn đặt hàng của chúng trong hàng đợi.priority queue is an abstract data type (ADT) which is like a regular queue or stack data structure, but where additionally each element has a priority associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

Mặc dù hàng đợi ưu tiên thường được thực hiện với đống, nhưng chúng khác biệt về mặt khái niệm với đống. Hàng đợi ưu tiên là một khái niệm trừu tượng như danh sách hoặc bản đồ; Cũng như một danh sách có thể được thực hiện với một danh sách được liên kết hoặc một mảng, một hàng đợi ưu tiên có thể được thực hiện với một đống hoặc một loạt các phương thức khác như một mảng không có thứ tự.heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like a list or a map; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.

từ hàng đợi ưu tiên wiki.

Mẫu A - Đơn giản nhất

Mã sau đây là cách sử dụng đơn giản nhất của hàng đợi ưu tiên.

try:
    import Queue as Q  # ver. < 3.0
except ImportError:
    import queue as Q

q = Q.PriorityQueue()
q.put(10)
q.put(1)
q.put(5)
while not q.empty():
	print q.get(),

Output:

1 5 10

Như chúng ta có thể thấy từ đầu ra, hàng đợi lưu trữ các phần tử theo mức độ ưu tiên không theo thứ tự tạo phần tử. Lưu ý rằng tùy thuộc vào các phiên bản Python, tên của hàng đợi ưu tiên là khác nhau. Vì vậy, chúng tôi đã sử dụng thử và ngoại trừ cặp để chúng tôi có thể điều chỉnh container của mình thành phiên bản.priority not by the order of element creation. Note that depending on the Python versions, the name of the priority queue is different. So, we used try and except pair so that we can adjust our container to the version.

Hàng đợi ưu tiên không chỉ lưu trữ các nguyên thủy tích hợp mà còn bất kỳ đối tượng nào như trong phần tiếp theo.

Mẫu B - Tuple

Hàng đợi ưu tiên có thể lưu trữ các đối tượng như Tuples:tuples:

try:
    import Queue as Q  # ver. < 3.0
except ImportError:
    import queue as Q

q = Q.PriorityQueue()
q.put((10,'ten'))
q.put((1,'one'))
q.put((5,'five'))
while not q.empty():
    print q.get(),

Output:

(1, 'one') (5, 'five') (10, 'ten')

Sample C - class objects using __cmp__()

Python không được gõ mạnh, vì vậy chúng tôi có thể lưu bất cứ thứ gì chúng tôi thích: giống như chúng tôi lưu trữ một bộ (ưu tiên, điều) trong phần trước. Chúng ta cũng có thể lưu trữ các đối tượng lớp nếu chúng ta ghi đè lên phương thức __cmp __ ():__cmp__() method:

try:
    import Queue as Q  # ver. < 3.0
except ImportError:
    import queue as Q

class Skill(object):
    def __init__(self, priority, description):
        self.priority = priority
        self.description = description
        print 'New Level:', description
        return
    def __cmp__(self, other):
        return cmp(self.priority, other.priority)

q = Q.PriorityQueue()

q.put(Skill(5, 'Proficient'))
q.put(Skill(10, 'Expert'))
q.put(Skill(1, 'Novice'))

while not q.empty():
    next_level = q.get()
    print 'Processing level:', next_level.description

Output:

New Level: Proficient
New Level: Expert
New Level: Novice
Processing level: Novice
Processing level: Proficient
Processing level: Expert

heapq - Heap queue

Heapq thực hiện một thuật toán sắp xếp min-heap phù hợp để sử dụng với danh sách của Python.

Mô -đun này cung cấp việc triển khai thuật toán hàng đợi Heap, còn được gọi là thuật toán hàng đợi ưu tiên.

Thoát nước là những cây nhị phân mà mọi nút cha mẹ đều có giá trị nhỏ hơn hoặc bằng với bất kỳ con nào của nó. Việc triển khai này sử dụng các mảng mà $ heap \ trái [k \ right] \ le heap \ left [2*k+1 \ right] $ và $ heap \ trái 2 \ Right] $ cho tất cả $ k $, đếm các phần tử từ không. Để so sánh, các yếu tố không tồn tại được coi là vô hạn. Thuộc tính thú vị của một đống là phần tử nhỏ nhất của nó luôn là gốc, $ heap \ trái [0 \ right] $.

Từ https://docs.python.org/2/l Library/heapq.html.

import heapq

heap = []
heapq.heappush(heap, (1, 'one'))
heapq.heappush(heap, (10, 'ten'))
heapq.heappush(heap, (5,'five'))

for x in heap:
	print x,
print

heapq.heappop(heap)

for x in heap:
	print x,
print 

# the smallest
print heap[0]

Output:

(1, 'one') (10, 'ten') (5, 'five')
(5, 'five') (10, 'ten')
(5, 'five')

heapq - heapify

Chúng ta có thể chuyển đổi danh sách $ x $ thành một đống, tại chỗ, trong thời gian tuyến tính:

heapq.heapify(x)

Ví dụ,

import heapq

heap = [(1, 'one'), (10, 'ten'), (5,'five')]
heapq.heapify(heap)
for x in heap:
	print x,
print

heap[1] = (9, 'nine')
for x in heap:
	print x,

Output:

1 5 10

Lưu ý rằng chúng tôi đã thay thế (10, 'mười') bằng (9, 'chín').

Có hàng đợi ưu tiên trong Python không?

Làm thế nào để bạn tạo một hàng đợi ưu tiên trong Python?

Là chủ đề hàng đợi ưu tiên python

Python có phải là hàng đợi ưu tiên không?