search

Hướng dẫn how does python heapq work? - python heapq hoạt động như thế nào?

1 năms trước
Trả lời: 0
Lượt xem: 88

Hàng đống và hàng đợi ưu tiên ít được biết đến nhưng đáng ngạc nhiên là các cấu trúc dữ liệu hữu ích. Đối với nhiều vấn đề liên quan đến việc tìm ra yếu tố tốt nhất trong bộ dữ liệu, họ cung cấp một giải pháp dễ sử dụng và hiệu quả cao. Mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 là một phần của thư viện tiêu chuẩn. Nó thực hiện tất cả các hoạt động Heap cấp thấp cũng như một số cách sử dụng phổ biến cấp cao cho đống. and priority queues are little-known but surprisingly useful data structures. For many problems that involve finding the best element in a dataset, they offer a solution that’s easy to use and highly effective. The Python 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 module is part of the standard library. It implements all the low-level heap operations as well as some high-level common uses for heaps.

Show

Hàng đợi ưu tiên là một công cụ mạnh mẽ có thể giải quyết các vấn đề khác nhau như viết một trình lập lịch email, tìm đường dẫn ngắn nhất trên bản đồ hoặc hợp nhất các tệp nhật ký. Lập trình có đầy đủ các vấn đề tối ưu hóa trong đó mục tiêu là tìm ra yếu tố tốt nhất. Hàng đợi ưu tiên và các chức năng trong mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 thường có thể giúp ích cho điều đó.

Trong hướng dẫn này, bạn sẽ học::

  • Hàng đợi hàng đống và ưu tiên là gì và chúng liên quan đến nhau như thế nàoheaps and priority queues are and how they relate to each other
  • Những loại vấn đề có thể được giải quyết bằng cách sử dụng một đốngproblems can be solved using a heap
  • Cách sử dụng mô -đun Python 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    5 để giải quyết những vấn đề đó
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    5 module     to solve those problems

Hướng dẫn này dành cho Pythonistas, những người thoải mái với danh sách, dicts, bộ và máy phát điện và đang tìm kiếm các cấu trúc dữ liệu tinh vi hơn.

Bạn có thể làm theo cùng với các ví dụ trong hướng dẫn này bằng cách tải xuống mã nguồn từ liên kết bên dưới:

Thức ăn là gì?

Các đống là cấu trúc dữ liệu cụ thể, trong khi hàng đợi ưu tiên là cấu trúc dữ liệu trừu tượng. Một cấu trúc dữ liệu trừu tượng xác định giao diện, trong khi cấu trúc dữ liệu cụ thể xác định việc triển khai.concrete data structures, whereas priority queues are abstract data structures. An abstract data structure determines the interface, while a concrete data structure defines the implementation.

Các đống thường được sử dụng để thực hiện hàng đợi ưu tiên. Họ là cấu trúc dữ liệu cụ thể phổ biến nhất để thực hiện cấu trúc dữ liệu trừu tượng hàng đợi ưu tiên.

Cấu trúc dữ liệu cụ thể cũng chỉ định đảm bảo hiệu suất. Hiệu suất đảm bảo xác định mối quan hệ giữa kích thước của cấu trúc và các hoạt động thời gian. Hiểu những đảm bảo đó cho phép bạn dự đoán chương trình sẽ mất bao nhiêu thời gian khi kích thước của đầu vào của nó thay đổi.performance guarantees. Performance guarantees define the relationship between the size of the structure and the time operations take. Understanding those guarantees allows you to predict how much time the program will take as the size of its inputs change.

Cấu trúc dữ liệu, đống và hàng đợi ưu tiên

Cấu trúc dữ liệu trừu tượng xác định các hoạt động và mối quan hệ giữa chúng. Ví dụ, cấu trúc dữ liệu trừu tượng hàng đợi ưu tiên hỗ trợ ba hoạt động:

  1. is_empty kiểm tra xem hàng đợi có trống không. checks whether the queue is empty.
  2. add_element thêm một phần tử vào hàng đợi. adds an element to the queue.
  3. Pop_element bật phần tử với mức độ ưu tiên cao nhất. pops the element with the highest priority.

Hàng đợi ưu tiên thường được sử dụng để tối ưu hóa việc thực hiện nhiệm vụ, trong đó mục tiêu là làm việc theo nhiệm vụ với mức độ ưu tiên cao nhất. Sau khi một nhiệm vụ được hoàn thành, mức độ ưu tiên của nó được hạ xuống và nó đã trở lại hàng đợi.

Có hai quy ước khác nhau để xác định mức độ ưu tiên của một yếu tố:

  1. Yếu tố lớn nhất có ưu tiên cao nhất.
  2. Yếu tố nhỏ nhất có ưu tiên cao nhất.

Hai quy ước này tương đương vì bạn luôn có thể đảo ngược thứ tự hiệu quả. Ví dụ: nếu các yếu tố của bạn bao gồm các số, thì sử dụng các số âm sẽ lật các quy ước xung quanh.

Mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 sử dụng quy ước thứ hai, thường là phổ biến hơn của hai. Theo quy ước này, yếu tố nhỏ nhất có mức độ ưu tiên cao nhất. Điều này nghe có vẻ đáng ngạc nhiên, nhưng nó thường khá hữu ích. Trong các ví dụ thực tế mà bạn sẽ thấy sau, quy ước này sẽ đơn giản hóa mã của bạn.

Cấu trúc dữ liệu cụ thể thực hiện các hoạt động được xác định trong cấu trúc dữ liệu trừu tượng và chỉ định thêm đảm bảo hiệu suất.

Việc triển khai HEAP của hàng đợi ưu tiên đảm bảo rằng cả hai phần tử đẩy (thêm) và popping (loại bỏ) là các hoạt động thời gian logarit. Điều này có nghĩa là thời gian cần thiết để thực hiện đẩy và pop tỷ lệ thuận với logarit cơ sở-2 của số lượng phần tử.logarithmic time operations. This means that the time it takes to do push and pop is proportional to the base-2 logarithm of the number of elements.

Logarit phát triển chậm. Logarit cơ sở-2 của mười lăm là khoảng bốn, trong khi logarit cơ sở-2 của một nghìn tỷ là khoảng bốn mươi. Điều này có nghĩa là nếu một thuật toán đủ nhanh trên mười lăm yếu tố, thì nó sẽ chỉ chậm hơn mười lần trên một nghìn tỷ yếu tố và có lẽ vẫn sẽ đủ nhanh.

Trong bất kỳ cuộc thảo luận nào về hiệu suất, cảnh báo lớn nhất là những cân nhắc trừu tượng này ít có ý nghĩa hơn so với thực sự đo lường một chương trình cụ thể và học tập ở nơi các tắc nghẽn. Đảm bảo hiệu suất chung vẫn rất quan trọng để đưa ra dự đoán hữu ích về hành vi của chương trình, nhưng những dự đoán đó cần được xác nhận.

Thực hiện đống

Một đống thực hiện một hàng đợi ưu tiên như một cây nhị phân hoàn chỉnh. Trong một cây nhị phân, mỗi nút sẽ có nhiều nhất là hai đứa trẻ. Trong một cây nhị phân hoàn chỉnh, tất cả các cấp ngoại trừ có thể là người sâu nhất luôn đầy đủ. Nếu mức độ sâu nhất không đầy đủ, thì nó sẽ có các nút càng xa bên trái càng tốt.complete binary tree. In a binary tree, each node will have at most two children. In a complete binary tree, all levels except possibly the deepest one are full at all times. If the deepest level is incomplete, then it will have the nodes as far to the left as possible.

Thuộc tính hoàn chỉnh có nghĩa là độ sâu của cây là logarit cơ sở-2 của số lượng phần tử, được làm tròn. Ở đây, một ví dụ về một cây nhị phân hoàn chỉnh:completeness property means that the depth of the tree is the base-2 logarithm of the number of elements, rounded up. Here’s an example of a complete binary tree:

Hướng dẫn how does python heapq work? - python heapq hoạt động như thế nào?

Trong ví dụ cụ thể này, tất cả các cấp độ đã hoàn thành. Mỗi nút ngoại trừ những cái sâu nhất có chính xác hai đứa con. Có tổng cộng bảy nút trong ba cấp độ. Ba là logarit cơ sở của bảy, làm tròn.

Nút đơn ở cấp cơ sở được gọi là nút gốc. Có vẻ kỳ lạ khi gọi nút ở đầu cây là gốc, nhưng đây là quy ước phổ biến trong lập trình và khoa học máy tính.root node. It might seem weird to call the node at the top of the tree the root, but this is the common convention in programming and computer science.

Hiệu suất đảm bảo trong một đống phụ thuộc vào cách các yếu tố kéo dài lên xuống cây. Kết quả thực tế của điều này là số lượng so sánh trong một đống là logarit cơ sở-2 của kích thước của cây.

Trong một cây đống, giá trị trong một nút luôn nhỏ hơn cả hai đứa con của nó. Đây được gọi là thuộc tính Heap. Điều này khác với cây tìm kiếm nhị phân, trong đó chỉ có nút bên trái sẽ nhỏ hơn giá trị của cha mẹ.heap property. This is different from a binary search tree, in which only the left node will be smaller than the value of its parent.

Các thuật toán cho cả đẩy và bật lên dựa vào việc vi phạm tạm thời thuộc tính heap, sau đó sửa chữa thuộc tính heap thông qua các so sánh và thay thế lên hoặc xuống một nhánh.

Ví dụ, để đẩy một phần tử lên một đống, Python thêm nút mới vào khe mở tiếp theo. Nếu lớp dưới cùng không đầy đủ, thì nút được thêm vào khe mở tiếp theo ở phía dưới. Mặt khác, một cấp độ mới được tạo và sau đó phần tử được thêm vào lớp dưới cùng mới.

Khi nút được thêm vào, Python so sánh nó với cha mẹ của nó. Nếu thuộc tính Heap bị vi phạm, thì nút và cha mẹ của nó được chuyển đổi và kiểm tra lại bắt đầu tại cha mẹ. Điều này tiếp tục cho đến khi thuộc tính heap giữ hoặc đã đạt được gốc.

Tương tự, khi bật phần tử nhỏ nhất, Python biết rằng, vì thuộc tính heap, phần tử nằm ở gốc cây. Nó thay thế phần tử bằng phần tử cuối cùng ở lớp sâu nhất và sau đó kiểm tra xem thuộc tính Heap có bị vi phạm chi nhánh không.

Việc sử dụng hàng đợi ưu tiên

Một hàng đợi ưu tiên, và một đống như một việc thực hiện hàng đợi ưu tiên, rất hữu ích cho các chương trình liên quan đến việc tìm kiếm một yếu tố cực đoan theo một cách nào đó. Ví dụ: bạn có thể sử dụng hàng đợi ưu tiên cho bất kỳ nhiệm vụ nào sau đây:

  • Nhận ba bài đăng trên blog phổ biến nhất từ ​​dữ liệu hit
  • Tìm cách nhanh nhất để đi từ điểm này sang điểm khác
  • Dự đoán xe buýt nào sẽ là người đầu tiên đến trạm dựa trên tần số đến

Một nhiệm vụ khác mà bạn có thể sử dụng hàng đợi ưu tiên là lên lịch email. Hãy tưởng tượng một hệ thống có một số loại email, mỗi loại cần được gửi ở một tần số nhất định. Một loại email cần phải đi ra sau mỗi mười lăm phút và một loại khác cần được gửi cứ sau bốn mươi phút.

Trình lập lịch có thể thêm cả hai loại email vào hàng đợi với dấu thời gian cho biết khi email tiếp theo cần được gửi. Sau đó, bộ lập lịch có thể nhìn vào phần tử với dấu thời gian nhỏ nhất chỉ định rằng nó tiếp theo là hàng tiếp theo được gửi và tính toán thời gian ngủ trước khi gửi.timestamp indicating when the email next needs to be sent. Then the scheduler could look at the element with the smallest timestamp—indicating that it’s next in line to be sent—and calculate how long to sleep before sending.

Khi bộ lập lịch thức dậy, nó sẽ xử lý email có liên quan, lấy email ra khỏi hàng đợi ưu tiên, tính toán dấu thời gian tiếp theo và đặt email lại vào hàng đợi tại vị trí chính xác.

Hàng đống như danh sách trong mô -đun Python >>> import heapq >>> a = [3, 5, 1, 2, 6, 8, 7] >>> heapq.heapify(a) >>> a [1, 2, 3, 5, 6, 8, 7] 5

Mặc dù bạn đã nhìn thấy đống được mô tả trước đó là một cái cây, nhưng điều quan trọng cần nhớ là nó là một cây nhị phân hoàn chỉnh. Tính đầy đủ có nghĩa là nó luôn luôn có thể cho biết có bao nhiêu yếu tố ở mỗi lớp ngoại trừ phần cuối cùng. Bởi vì điều này, đống có thể được thực hiện như một danh sách. Đây là những gì mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 làm.

Có ba quy tắc xác định mối quan hệ giữa phần tử tại chỉ mục 

>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
1 và các yếu tố xung quanh của nó:

  1. Đứa con đầu lòng của nó là ở 
    >>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
    2.
  2. Đứa con thứ hai của nó là 
    >>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
    3.
  3. Cha mẹ của nó ở 
    >>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
    4.

Các quy tắc trên cho bạn biết cách trực quan hóa một danh sách như một cây nhị phân hoàn chỉnh. Hãy nhớ rằng một yếu tố luôn có cha mẹ, nhưng một số yếu tố không có con. Nếu 

>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
5 vượt quá cuối danh sách, thì yếu tố này không có con. Nếu 
>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
2 là một chỉ số hợp lệ nhưng 
>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
3 thì không, thì phần tử chỉ có một đứa trẻ.

Thuộc tính Heap có nghĩa là nếu 

>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
8 là một đống, thì những điều sau đây sẽ không bao giờ là 
>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
9:

h[k] <= h[2*k + 1] and h[k] <= h[2*k + 2]

Nó có thể tăng 

>>> import heapq
>>> a = [2, 5, 3, 7, 6, 8]
>>> heapq.heappush(a, 4)
>>> a
[2, 5, 3, 7, 6, 8, 4]
>>> heapq.heappop(a)
2
>>> heapq.heappop(a)
3
>>> heapq.heappop(a)
4
0 nếu bất kỳ chỉ số nào vượt quá độ dài của danh sách, nhưng nó sẽ không bao giờ là 
>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
9.

Nói cách khác, một phần tử phải luôn nhỏ hơn các phần tử ở hai lần chỉ số cộng với một và hai lần chỉ số của nó cộng với hai.

Ở đây, một hình ảnh của một danh sách thỏa mãn thuộc tính Heap:

Hướng dẫn how does python heapq work? - python heapq hoạt động như thế nào?

Các mũi tên đi từ phần tử 

>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
1 đến các phần tử 
>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
2 và 
>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
3. Ví dụ: phần tử đầu tiên trong danh sách Python có chỉ mục 
>>> import heapq
>>> a = [2, 5, 3, 7, 6, 8]
>>> heapq.heappush(a, 4)
>>> a
[2, 5, 3, 7, 6, 8, 4]
>>> heapq.heappop(a)
2
>>> heapq.heappop(a)
3
>>> heapq.heappop(a)
4
5, do đó, hai mũi tên của nó tại các chỉ số 
>>> import heapq
>>> a = [2, 5, 3, 7, 6, 8]
>>> heapq.heappush(a, 4)
>>> a
[2, 5, 3, 7, 6, 8, 4]
>>> heapq.heappop(a)
2
>>> heapq.heappop(a)
3
>>> heapq.heappop(a)
4
6 và 
>>> import heapq
>>> a = [2, 5, 3, 7, 6, 8]
>>> heapq.heappush(a, 4)
>>> a
[2, 5, 3, 7, 6, 8, 4]
>>> heapq.heappop(a)
2
>>> heapq.heappop(a)
3
>>> heapq.heappop(a)
4
7. Lưu ý cách các mũi tên luôn đi từ giá trị nhỏ hơn sang giá trị lớn hơn. Đây là cách bạn có thể kiểm tra xem danh sách có thỏa mãn thuộc tính Heap không.

Hoạt động cơ bản

Mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 thực hiện các hoạt động HEAP trong danh sách. Không giống như nhiều mô -đun khác, nó không xác định một lớp tùy chỉnh. Mô -đun Python 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 có các chức năng hoạt động trực tiếp trong danh sách.

Thông thường, như trong ví dụ email ở trên, các phần tử sẽ được chèn vào một đống từng cái một, bắt đầu bằng một đống trống. Tuy nhiên, nếu có một danh sách các yếu tố cần phải là một đống, thì mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 bao gồm 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
1 để biến danh sách thành một đống hợp lệ.

Mã sau sử dụng 

import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
1 để biến 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
3 thành một đống:heap:

>>>

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]

Bạn có thể kiểm tra xem mặc dù 

import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
4 xuất hiện sau 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
5, danh sách 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
3 vẫn tuân theo tài sản của Heap. Ví dụ, 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
7, là 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
8, nhỏ hơn 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
9, đó là 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
4.

Như bạn có thể thấy, 

import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
1 sửa đổi danh sách tại chỗ nhưng không sắp xếp nó. Một đống không phải được sắp xếp để đáp ứng tài sản Heap. Tuy nhiên, vì mọi danh sách được sắp xếp đều thỏa mãn thuộc tính Heap, chạy 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
1 trong danh sách được sắp xếp won Thay đổi thứ tự các yếu tố trong danh sách.

Các hoạt động cơ bản khác trong mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 cho rằng danh sách đã là một đống. Nó rất hữu ích khi lưu ý rằng một danh sách trống hoặc danh sách độ dài mà người ta sẽ luôn là một đống.

Vì gốc của cây là phần tử đầu tiên, bạn không cần một chức năng chuyên dụng để đọc phần tử nhỏ nhất không phá hủy. Phần tử đầu tiên, 

>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
4, sẽ luôn là yếu tố nhỏ nhất.

Để bật phần tử nhỏ nhất trong khi bảo quản thuộc tính Heap, mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 xác định 
>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
6.

Tại đây, cách sử dụng 

>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
6 để bật một yếu tố:

>>>

>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]


>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]

Bạn có thể kiểm tra xem mặc dù 

import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
4 xuất hiện sau 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
5, danh sách 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
3 vẫn tuân theo tài sản của Heap. Ví dụ, 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
7, là 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
8, nhỏ hơn 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
9, đó là 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
4.

Như bạn có thể thấy, 

import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
1 sửa đổi danh sách tại chỗ nhưng không sắp xếp nó. Một đống không phải được sắp xếp để đáp ứng tài sản Heap. Tuy nhiên, vì mọi danh sách được sắp xếp đều thỏa mãn thuộc tính Heap, chạy 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
1 trong danh sách được sắp xếp won Thay đổi thứ tự các yếu tố trong danh sách.

>>>

>>> import heapq
>>> a = [2, 5, 3, 7, 6, 8]
>>> heapq.heappush(a, 4)
>>> a
[2, 5, 3, 7, 6, 8, 4]
>>> heapq.heappop(a)
2
>>> heapq.heappop(a)
3
>>> heapq.heappop(a)
4


>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]

Bạn có thể kiểm tra xem mặc dù 

import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
4 xuất hiện sau 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
5, danh sách 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
3 vẫn tuân theo tài sản của Heap. Ví dụ, 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
7, là 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
8, nhỏ hơn 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
9, đó là 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
4.

  1. Như bạn có thể thấy, 
    import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
    1 sửa đổi danh sách tại chỗ nhưng không sắp xếp nó. Một đống không phải được sắp xếp để đáp ứng tài sản Heap. Tuy nhiên, vì mọi danh sách được sắp xếp đều thỏa mãn thuộc tính Heap, chạy 
    import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
    1 trong danh sách được sắp xếp won Thay đổi thứ tự các yếu tố trong danh sách.     is equivalent to 
    >>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
    6 followed by 
    >>> import heapq
>>> results="""\
... Christania Williams      11.80
... Marie-Josee Ta Lou       10.86
... Elaine Thompson          10.71
... Tori Bowie               10.83
... Shelly-Ann Fraser-Pryce  10.86
... English Gardner          10.94
... Michelle-Lee Ahye        10.92
... Dafne Schippers          10.90
... """
>>> top_3 = heapq.nsmallest(
...     3, results.splitlines(), key=lambda x: float(x.split()[-1])
... )
>>> print("\n".join(top_3))
Elaine Thompson          10.71
Tori Bowie               10.83
Marie-Josee Ta Lou       10.86
    5.
  2. Các hoạt động cơ bản khác trong mô -đun Python 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    5 cho rằng danh sách đã là một đống. Nó rất hữu ích khi lưu ý rằng một danh sách trống hoặc danh sách độ dài mà người ta sẽ luôn là một đống.     is equivalent to 
    >>> import heapq
>>> results="""\
... Christania Williams      11.80
... Marie-Josee Ta Lou       10.86
... Elaine Thompson          10.71
... Tori Bowie               10.83
... Shelly-Ann Fraser-Pryce  10.86
... English Gardner          10.94
... Michelle-Lee Ahye        10.92
... Dafne Schippers          10.90
... """
>>> top_3 = heapq.nsmallest(
...     3, results.splitlines(), key=lambda x: float(x.split()[-1])
... )
>>> print("\n".join(top_3))
Elaine Thompson          10.71
Tori Bowie               10.83
Marie-Josee Ta Lou       10.86
    5 followed by 
    >>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
    6.

Vì gốc của cây là phần tử đầu tiên, bạn không cần một chức năng chuyên dụng để đọc phần tử nhỏ nhất không phá hủy. Phần tử đầu tiên, 

>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
4, sẽ luôn là yếu tố nhỏ nhất.

Để bật phần tử nhỏ nhất trong khi bảo quản thuộc tính Heap, mô -đun Python >>> import heapq >>> a = [3, 5, 1, 2, 6, 8, 7] >>> heapq.heapify(a) >>> a [1, 2, 3, 5, 6, 8, 7] 5 xác định >>> for _ in range(10): ... print(next(element)) (datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email') (datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email') (datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email') (datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email') (datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email') (datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email') (datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email') (datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email') (datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email') (datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email') 6.

Tại đây, cách sử dụng 

>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
6 để bật một yếu tố:iterator, not a list.

Hàm trả về phần tử đầu tiên, 

>>> import heapq
>>> a = [2, 5, 3, 7, 6, 8]
>>> heapq.heappush(a, 4)
>>> a
[2, 5, 3, 7, 6, 8, 4]
>>> heapq.heappop(a)
2
>>> heapq.heappop(a)
3
>>> heapq.heappop(a)
4
6 và bảo tồn thuộc tính Heap trên 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
3. Ví dụ, 
>>> import heapq
>>> results="""\
... Christania Williams      11.80
... Marie-Josee Ta Lou       10.86
... Elaine Thompson          10.71
... Tori Bowie               10.83
... Shelly-Ann Fraser-Pryce  10.86
... English Gardner          10.94
... Michelle-Lee Ahye        10.92
... Dafne Schippers          10.90
... """
>>> top_3 = heapq.nsmallest(
...     3, results.splitlines(), key=lambda x: float(x.split()[-1])
... )
>>> print("\n".join(top_3))
Elaine Thompson          10.71
Tori Bowie               10.83
Marie-Josee Ta Lou       10.86
0 là 
>>> import heapq
>>> results="""\
... Christania Williams      11.80
... Marie-Josee Ta Lou       10.86
... Elaine Thompson          10.71
... Tori Bowie               10.83
... Shelly-Ann Fraser-Pryce  10.86
... English Gardner          10.94
... Michelle-Lee Ahye        10.92
... Dafne Schippers          10.90
... """
>>> top_3 = heapq.nsmallest(
...     3, results.splitlines(), key=lambda x: float(x.split()[-1])
... )
>>> print("\n".join(top_3))
Elaine Thompson          10.71
Tori Bowie               10.83
Marie-Josee Ta Lou       10.86
1 và 
>>> import heapq
>>> results="""\
... Christania Williams      11.80
... Marie-Josee Ta Lou       10.86
... Elaine Thompson          10.71
... Tori Bowie               10.83
... Shelly-Ann Fraser-Pryce  10.86
... English Gardner          10.94
... Michelle-Lee Ahye        10.92
... Dafne Schippers          10.90
... """
>>> top_3 = heapq.nsmallest(
...     3, results.splitlines(), key=lambda x: float(x.split()[-1])
... )
>>> print("\n".join(top_3))
Elaine Thompson          10.71
Tori Bowie               10.83
Marie-Josee Ta Lou       10.86
2 là 
>>> import heapq
>>> results="""\
... Christania Williams      11.80
... Marie-Josee Ta Lou       10.86
... Elaine Thompson          10.71
... Tori Bowie               10.83
... Shelly-Ann Fraser-Pryce  10.86
... English Gardner          10.94
... Michelle-Lee Ahye        10.92
... Dafne Schippers          10.90
... """
>>> top_3 = heapq.nsmallest(
...     3, results.splitlines(), key=lambda x: float(x.split()[-1])
... )
>>> print("\n".join(top_3))
Elaine Thompson          10.71
Tori Bowie               10.83
Marie-Josee Ta Lou       10.86
3.

import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)

Mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 cũng bao gồm 
>>> import heapq
>>> results="""\
... Christania Williams      11.80
... Marie-Josee Ta Lou       10.86
... Elaine Thompson          10.71
... Tori Bowie               10.83
... Shelly-Ann Fraser-Pryce  10.86
... English Gardner          10.94
... Michelle-Lee Ahye        10.92
... Dafne Schippers          10.90
... """
>>> top_3 = heapq.nsmallest(
...     3, results.splitlines(), key=lambda x: float(x.split()[-1])
... )
>>> print("\n".join(top_3))
Elaine Thompson          10.71
Tori Bowie               10.83
Marie-Josee Ta Lou       10.86
5 để đẩy một phần tử vào đống trong khi bảo quản thuộc tính heap.

Ví dụ sau đây cho thấy việc đẩy giá trị lên một đống:

>>>

>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')


>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]

Bạn có thể kiểm tra xem mặc dù 

import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
4 xuất hiện sau 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
5, danh sách 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
3 vẫn tuân theo tài sản của Heap. Ví dụ, 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
7, là 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
8, nhỏ hơn 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
9, đó là 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
4.

Như bạn có thể thấy, 

import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
1 sửa đổi danh sách tại chỗ nhưng không sắp xếp nó. Một đống không phải được sắp xếp để đáp ứng tài sản Heap. Tuy nhiên, vì mọi danh sách được sắp xếp đều thỏa mãn thuộc tính Heap, chạy 
import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
1 trong danh sách được sắp xếp won Thay đổi thứ tự các yếu tố trong danh sách.

Các hoạt động cơ bản khác trong mô -đun Python >>> import heapq >>> a = [3, 5, 1, 2, 6, 8, 7] >>> heapq.heapify(a) >>> a [1, 2, 3, 5, 6, 8, 7] 5 cho rằng danh sách đã là một đống. Nó rất hữu ích khi lưu ý rằng một danh sách trống hoặc danh sách độ dài mà người ta sẽ luôn là một đống.

Vì gốc của cây là phần tử đầu tiên, bạn không cần một chức năng chuyên dụng để đọc phần tử nhỏ nhất không phá hủy. Phần tử đầu tiên, 

>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
4, sẽ luôn là yếu tố nhỏ nhất.

Để bật phần tử nhỏ nhất trong khi bảo quản thuộc tính Heap, mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 xác định 
>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
6.

Tại đây, cách sử dụng 

>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
6 để bật một yếu tố:

>>>

>>> import heapq
>>> results="""\
... Christania Williams      11.80
... Marie-Josee Ta Lou       10.86
... Elaine Thompson          10.71
... Tori Bowie               10.83
... Shelly-Ann Fraser-Pryce  10.86
... English Gardner          10.94
... Michelle-Lee Ahye        10.92
... Dafne Schippers          10.90
... """
>>> top_3 = heapq.nsmallest(
...     3, results.splitlines(), key=lambda x: float(x.split()[-1])
... )
>>> print("\n".join(top_3))
Elaine Thompson          10.71
Tori Bowie               10.83
Marie-Josee Ta Lou       10.86


>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]

  1. Bạn có thể kiểm tra xem mặc dù 
    import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
    4 xuất hiện sau 
    import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
    5, danh sách 
    import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
    3 vẫn tuân theo tài sản của Heap. Ví dụ, 
    import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
    7, là 
    import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
    8, nhỏ hơn 
    import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
    9, đó là 
    import datetime
import heapq

def email(frequency, details):
    current = datetime.datetime.now()
    while True:
        current += frequency
        yield current, details

fast_email = email(datetime.timedelta(minutes=15), "fast email")
slow_email = email(datetime.timedelta(minutes=40), "slow email")

unified = heapq.merge(fast_email, slow_email)
    4.     indicates how many elements to return.
  2. def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
    3 Xác định các phần tử hoặc tập dữ liệu để so sánh.     identifies the elements or dataset to compare.
  3. def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
    4 là một hàm có thể gọi được xác định cách so sánh các yếu tố.     is a callable function that determines how elements are compared.

Ở đây, hàm 

def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
4 chia dòng theo khoảng trắng, lấy phần tử cuối cùng và chuyển đổi nó thành số điểm nổi. Điều này có nghĩa là mã sẽ sắp xếp các dòng theo thời gian chạy và trả về ba dòng với thời gian chạy nhỏ nhất. Những điều này tương ứng với ba vận động viên nhanh nhất, mang lại cho bạn những người chiến thắng huy chương vàng, bạc và đồng.

Mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 cũng bao gồm 
def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
7, có các tham số tương tự và trả về các yếu tố lớn nhất. Điều này sẽ hữu ích nếu bạn muốn có được các huy chương từ cuộc thi ném Javelin, trong đó mục tiêu là ném javelin càng xa càng tốt.

Cách xác định vấn đề

Một đống, như một việc thực hiện hàng đợi ưu tiên, là một công cụ tốt để giải quyết các vấn đề liên quan đến các thái cực, giống như nhất hoặc ít nhất của một số liệu nhất định.

Có những từ khác chỉ ra một đống có thể hữu ích:

  • Lớn nhất
  • Nhỏ nhất
  • To nhất
  • Nhỏ nhất
  • To nhất
  • Tốt nhất
  • Tồi tệ nhất
  • Đứng đầu
  • Đáy
  • Tối đa
  • Tối thiểu

Tối ưu

Bất cứ khi nào một tuyên bố vấn đề chỉ ra rằng bạn đang tìm kiếm một số yếu tố cực đoan, thì nó có giá trị khi nghĩ về việc liệu một hàng đợi ưu tiên sẽ hữu ích hay không.

Đôi khi hàng đợi ưu tiên sẽ chỉ là một phần của giải pháp và phần còn lại sẽ là một số biến thể về lập trình động. Đây là trường hợp với ví dụ đầy đủ mà bạn sẽ thấy trong phần tiếp theo. Lập trình động và hàng đợi ưu tiên thường hữu ích với nhau.

Ví dụ: Tìm đường dẫn

Ví dụ sau đây đóng vai trò là trường hợp sử dụng thực tế cho mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5. Ví dụ sẽ sử dụng một thuật toán cổ điển, như một phần của nó, đòi hỏi một đống. Bạn có thể tải xuống mã nguồn được sử dụng trong các ví dụ bằng cách nhấp vào liên kết bên dưới:

Hãy tưởng tượng một robot cần điều hướng một mê cung hai chiều. Robot cần phải đi từ gốc, được đặt ở góc trên cùng bên trái, đến đích ở góc dưới bên phải. Robot có một bản đồ của mê cung trong bộ nhớ của nó, vì vậy nó có thể lên kế hoạch cho toàn bộ đường dẫn trước khi đặt ra.

Mục tiêu là để robot hoàn thành mê cung càng nhanh càng tốt.

  1. Thuật toán của chúng tôi là một biến thể của thuật toán Dijkstra. Có ba cấu trúc dữ liệu được lưu giữ và cập nhật trong suốt thuật toán: is a map of a tentative path from the origin to a position, 

    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    00. The path is called tentative because it’s the shortest known path, but it might be improved upon.

  2. def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
    9 là bản đồ của một con đường dự kiến ​​từ nguồn gốc đến một vị trí, 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    00. Con đường được gọi là dự kiến ​​bởi vì nó là con đường ngắn nhất được biết đến, nhưng nó có thể được cải thiện.     is set of points for which the path that 
    def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
    9 maps is certain to be the shortest possible path.

  3. >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    01 là bộ điểm mà đường dẫn mà 
    def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
    9 bản đồ chắc chắn là đường dẫn ngắn nhất có thể.     is a heap of positions that have a path. The sorting key of the heap is the length of the path.

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
03 là một đống các vị trí có đường dẫn. Phím phân loại của đống là chiều dài của đường dẫn.

  1. Ở mỗi bước, bạn thực hiện tối đa bốn hành động:

  2. Pop một ứng cử viên từ 

    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    03.

  3. Thêm ứng viên vào bộ 

    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    01. Nếu ứng viên đã là thành viên của bộ 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    01, thì hãy bỏ qua hai hành động tiếp theo.

  4. Tìm con đường ngắn nhất được biết đến đến ứng cử viên hiện tại.

Đối với mỗi ứng cử viên hiện tại của các nước láng giềng ngay lập tức, hãy xem liệu việc đi qua ứng cử viên có đưa ra một con đường ngắn hơn đường dẫn 

def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
9 hiện tại không. Nếu vậy, sau đó cập nhật đường dẫn 
def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
9 và đống 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
03 với đường dẫn mới này.

Các bước được chạy trong một vòng lặp cho đến khi đích được thêm vào bộ >>> import heapq >>> a = [3, 5, 1, 2, 6, 8, 7] >>> heapq.heapify(a) >>> a [1, 2, 3, 5, 6, 8, 7] 01. Khi đích đến trong bộ >>> import heapq >>> a = [3, 5, 1, 2, 6, 8, 7] >>> heapq.heapify(a) >>> a [1, 2, 3, 5, 6, 8, 7] 01, bạn đã hoàn thành. Đầu ra của thuật toán là đường dẫn def is_valid(lines, position): x, y = position if not (0 <= y < len(lines) and 0 <= x < len(lines[y])): return False if lines[y][x] == "X": return False return True 9 đến đích, hiện là >>> import heapq >>> a = [3, 5, 1, 2, 6, 8, 7] >>> heapq.heapify(a) >>> a [1, 2, 3, 5, 6, 8, 7] 01 là đường dẫn ngắn nhất có thể.

Mã cấp cao nhất

Bây giờ bạn đã hiểu thuật toán, đã đến lúc viết mã để thực hiện nó. Trước khi thực hiện thuật toán, nó rất hữu ích để viết một số mã hỗ trợ.

Đầu tiên, bạn cần nhập mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5:

Bạn sẽ sử dụng các chức năng từ mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 để duy trì một đống sẽ giúp bạn tìm thấy vị trí với đường dẫn ngắn nhất được biết đến ở mỗi lần lặp.

map = """\
.......X..
.......X..
....XXXX..
..........
..........
"""

Bước tiếp theo là xác định bản đồ là một biến trong mã:

Bản đồ là một chuỗi được trích dẫn ba cho thấy khu vực mà robot có thể di chuyển cũng như bất kỳ chướng ngại vật nào.

Mặc dù một kịch bản thực tế hơn sẽ khiến bạn đọc bản đồ từ một tệp, nhưng với mục đích giảng dạy, nó dễ dàng hơn để xác định một biến trong mã bằng bản đồ đơn giản này. Mã này sẽ hoạt động trên bất kỳ bản đồ nào, nhưng nó dễ hiểu và gỡ lỗi hơn trên bản đồ đơn giản.

Mã hỗ trợ

Hàm đầu tiên sẽ chuyển đổi bản đồ thành một cái gì đó dễ phân tích mã hơn trong mã. 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
18 Nhận bản đồ và phân tích nó:

def parse_map(map):
    lines = map.splitlines()
    origin = 0, 0
    destination = len(lines[-1]) - 1, len(lines) - 1
    return lines, origin, destination

Chức năng lấy bản đồ và trả về một bộ ba yếu tố:

  1. Danh sách 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    19
  2. >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    20
  3. >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    21

Điều này cho phép phần còn lại của mã hoạt động trên các cấu trúc dữ liệu được thiết kế cho máy tính, không phải cho con người có khả năng quét trực quan.

Danh sách 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
19 có thể được lập chỉ mục bởi tọa độ 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
23. Biểu thức 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
24 trả về giá trị của vị trí là một trong hai ký tự:

  1. Một dấu chấm (
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    25) cho biết vị trí là một khoảng trống.     indicates the position is an empty space.
  2. Chữ 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    26 chỉ ra vị trí này là một trở ngại.     indicates the position is an obstacle.

Điều này sẽ hữu ích khi bạn muốn tìm vị trí mà robot có thể chiếm giữ.

Hàm 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
27 tính toán xem vị trí 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
23 đã cho là hợp lệ:

def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True

Hàm này có hai đối số:

  1. >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    19 là bản đồ như một danh sách các dòng.     is the map as a list of lines.
  2. >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    30 là vị trí cần kiểm tra dưới dạng hai số nguyên cho biết tọa độ 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    23.     is the position to check as a two-tuple of integers indicating the 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    23 coordinates.

Để có hiệu lực, một vị trí phải nằm trong ranh giới của bản đồ chứ không phải là một trở ngại.

Hàm kiểm tra xem 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
32 có hiệu lực bằng cách kiểm tra độ dài của danh sách 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
19. Hàm tiếp theo kiểm tra rằng 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
34 có giá trị bằng cách đảm bảo nó bên trong 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
35. Cuối cùng, bây giờ bạn đã biết cả hai tọa độ đều ở trong bản đồ, mã kiểm tra xem họ không phải là một trở ngại bằng cách nhìn vào nhân vật ở vị trí này và so sánh ký tự với 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
26.

Một người trợ giúp hữu ích khác là 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
37, tìm thấy tất cả các hàng xóm của một vị trí:

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
0

Hàm trả về tất cả các vị trí hợp lệ xung quanh vị trí hiện tại.

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
37 cẩn thận để tránh xác định vị trí là hàng xóm của chính mình, nhưng nó cho phép hàng xóm chéo. Đây là lý do tại sao ít nhất một trong số 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
39 và 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
40 không được bằng không, nhưng nó không sao cho cả hai người khác không.

Hàm trợ giúp cuối cùng là 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
41, tìm thấy các đường dẫn ngắn hơn:

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
1

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
41 mang lại các vị trí mà đường dẫn có 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
43 là bước cuối cùng của nó ngắn hơn đường dẫn đã biết hiện tại.

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
41 có ba tham số:

  1. def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
    9 là một bản đồ từ điển một vị trí cho con đường ngắn nhất được biết đến.     is a dictionary mapping a position to the shortest known path.
  2. >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    46 là một vị trí có thể lặp lại mà bạn muốn rút ngắn đường dẫn.     is an iterable of positions to which you want to shorten the path.
  3. >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    43 là vị trí mà qua đó, có lẽ, một con đường ngắn hơn đến 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    46 có thể được tìm thấy.     is the position through which, perhaps, a shorter path to the 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    46 can be found.

Giả định là tất cả các yếu tố trong 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
46 có thể đạt được trong một bước từ 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
43.

Hàm 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
41 kiểm tra xem 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
43 làm bước cuối cùng sẽ tạo đường dẫn tốt hơn cho từng vị trí. Nếu không có đường dẫn đến một vị trí, thì bất kỳ đường dẫn nào cũng ngắn hơn. Nếu có một đường dẫn đã biết, thì bạn chỉ mang lại đường dẫn mới nếu chiều dài của nó ngắn hơn. Để làm cho API của 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
41 dễ sử dụng hơn, một phần của 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
54 cũng là đường dẫn ngắn hơn.

Tất cả các hàm trợ giúp được viết là các hàm thuần túy, có nghĩa là chúng không sửa đổi bất kỳ cấu trúc dữ liệu nào và chỉ trả về các giá trị. Điều này giúp việc tuân theo thuật toán cốt lõi dễ dàng hơn, tất cả các bản cập nhật cấu trúc dữ liệu.pure functions, meaning they don’t modify any data structures and only return values. This makes it easier to follow the core algorithm, which does all the data structure updates.

Mã thuật toán cốt lõi

Để tóm tắt lại, bạn đã tìm kiếm con đường ngắn nhất giữa nguồn gốc và đích đến.

Bạn giữ ba phần dữ liệu:

  1. >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    01 là tập hợp các vị trí nhất định.     is the set of certain positions.
  2. >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    03 là đống ứng cử viên.     is the heap of candidates.
  3. def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
    9 là một nút ánh xạ từ điển đến đường dẫn ngắn nhất hiện tại.     is a dictionary mapping nodes to the current shortest known path.

Một vị trí nằm trong 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
01 nếu bạn có thể chắc chắn rằng đường dẫn ngắn nhất được biết là đường dẫn ngắn nhất có thể. Nếu đích đến trong bộ 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
01, thì đường dẫn ngắn nhất đã biết đến đích là không nghi ngờ gì là đường dẫn ngắn nhất có thể và bạn có thể trả về đường dẫn này.

Hàng đống 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
03 được tổ chức theo chiều dài của đường dẫn đã biết ngắn nhất và được quản lý với sự trợ giúp của các chức năng trong mô -đun Python 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5.

Ở mỗi bước, bạn nhìn vào ứng cử viên với con đường ngắn nhất được biết đến. Đây là nơi mà đống đang được xuất hiện với 

>>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
6. Không có đường dẫn ngắn hơn đến ứng cử viên này, tất cả các đường dẫn khác đi qua một số nút khác trong 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
03 và tất cả những điều này đều dài hơn. Do đó, ứng cử viên hiện tại có thể được đánh dấu 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
01.

Sau đó, bạn nhìn vào tất cả các hàng xóm chưa được truy cập và nếu đi qua nút hiện tại là một cải tiến, thì bạn thêm chúng vào đống 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
03 bằng cách sử dụng 
>>> import heapq
>>> results="""\
... Christania Williams      11.80
... Marie-Josee Ta Lou       10.86
... Elaine Thompson          10.71
... Tori Bowie               10.83
... Shelly-Ann Fraser-Pryce  10.86
... English Gardner          10.94
... Michelle-Lee Ahye        10.92
... Dafne Schippers          10.90
... """
>>> top_3 = heapq.nsmallest(
...     3, results.splitlines(), key=lambda x: float(x.split()[-1])
... )
>>> print("\n".join(top_3))
Elaine Thompson          10.71
Tori Bowie               10.83
Marie-Josee Ta Lou       10.86
5.

Hàm 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
67 thực hiện thuật toán này:

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
2

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
67 nhận được 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
69 dưới dạng chuỗi và trả lại đường dẫn từ gốc đến đích dưới dạng danh sách các vị trí.

Chức năng này hơi dài và phức tạp, vì vậy hãy để Lừa đi qua nó một chút:

  • Các dòng 2 đến 5 Thiết lập các biến mà vòng lặp sẽ xem và cập nhật. Bạn đã biết một đường dẫn từ gốc đến chính nó, đó là con đường trống, có độ dài 0. set up the variables that the loop will look at and update. You already know a path from the origin to itself, which is the empty path, of length 0.

  • Dòng 6 xác định điều kiện chấm dứt vòng lặp. Nếu không có 

    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    03, thì không có đường dẫn nào có thể được rút ngắn. Nếu 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    21 nằm trong 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    01, thì đường dẫn đến 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    21 có thể được thực hiện ngắn hơn.     defines the loop’s termination condition. If there are no 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    03, then no paths can be shortened. If 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    21 is in 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    01, then the path to 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    21 can’t be made shorter.

  • Các dòng 7 đến 10 Nhận một ứng cử viên sử dụng 

    >>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
    6, bỏ qua vòng lặp nếu nó đã ở trong 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    01 và nếu không thì thêm ứng cử viên vào 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    01. Điều này đảm bảo mọi ứng cử viên sẽ được xử lý bởi vòng lặp nhiều nhất một lần.     get a candidate using 
    >>> for _ in range(10):
...    print(next(element))
(datetime.datetime(2020, 4, 12, 21, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 21, 52, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 21, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 12, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 27, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 32, 20, 305360), 'slow email')
(datetime.datetime(2020, 4, 12, 22, 42, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 22, 57, 20, 305358), 'fast email')
(datetime.datetime(2020, 4, 12, 23, 12, 20, 305358), 'fast email')
    6, skip the loop if it’s already in 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    01, and otherwise add the candidate to 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    01. This makes sure every candidate will be processed by the loop at most once.

  • Các dòng 11 đến 15 Sử dụng 

    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    37 và 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    41 để tìm các đường dẫn ngắn hơn đến các vị trí lân cận và cập nhật từ điển 
    def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
    9 và 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    03.     use 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    37 and 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    41 to find shorter paths to neighboring positions and update the 
    def is_valid(lines, position):
    x, y = position
    if not (0 <= y < len(lines) and 0 <= x < len(lines[y])):
        return False
    if lines[y][x] == "X":
        return False
    return True
    9 dictionary and 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    03 heap.

  • Các dòng 16 đến 19 liên quan đến việc trả lại kết quả chính xác. Nếu một đường dẫn được tìm thấy, thì hàm sẽ trả lại nó. Mặc dù tính toán các đường dẫn mà không có vị trí cuối cùng khiến việc thực hiện thuật toán đơn giản hơn, nhưng nó lại là một API đẹp hơn để trả về nó với đích đến. Nếu không tìm thấy đường dẫn, thì một ngoại lệ được nâng lên. deal with returning the correct result. If a path was found, then the function will return it. Although computing the paths without the final position made implementing the algorithm simpler, it’s a nicer API to return it with the destination. If no path is found, then an exception is raised.

Phá vỡ chức năng thành các phần riêng biệt cho phép bạn hiểu nó tại một thời điểm.

Mã trực quan

Nếu thuật toán thực sự được sử dụng bởi một robot, thì robot có thể sẽ hoạt động tốt hơn với một danh sách các vị trí mà nó sẽ đi qua. Tuy nhiên, để làm cho kết quả tốt hơn cho con người, sẽ tốt hơn để hình dung chúng.

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
81 vẽ một đường dẫn trên bản đồ:

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
3

Hàm lấy 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
82 và 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
69 làm tham số. Nó trả về một bản đồ mới với đường dẫn được biểu thị bằng biểu tượng AT (
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
84).

Chạy mã

Cuối cùng, bạn cần gọi các chức năng. Điều này có thể được thực hiện từ trình thông dịch tương tác Python.

Mã sau đây sẽ chạy thuật toán và hiển thị đầu ra đẹp:

>>>

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
4

Đầu tiên bạn nhận được con đường ngắn nhất từ ​​

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
67. Sau đó, bạn chuyển nó sang 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
81 để hiển thị bản đồ với đường dẫn được đánh dấu trên nó. Cuối cùng, bạn 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
87 Bản đồ đến đầu ra tiêu chuẩn.

Đường dẫn di chuyển một bước sang phải, sau đó một vài bước chéo về phía dưới cùng bên phải, sau đó thêm một vài bước bên phải, và cuối cùng nó kết thúc với một bước chéo đến phía dưới bên phải.

Xin chúc mừng! Bạn đã giải quyết một vấn đề bằng cách sử dụng mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5.

Những loại vấn đề gây bệnh này, có thể giải quyết được bằng sự kết hợp giữa lập trình động và hàng đợi ưu tiên, là phổ biến trong các cuộc phỏng vấn việc làm và các thách thức lập trình. Ví dụ, sự ra đời năm 2019 của mã bao gồm một vấn đề có thể được giải quyết với các kỹ thuật được mô tả ở đây.

Sự kết luận

Bây giờ bạn biết các cấu trúc dữ liệu hàng đợi hàng hóa và ưu tiên là gì và loại vấn đề nào mà họ hữu ích trong việc giải quyết. Bạn đã học cách sử dụng mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 để sử dụng danh sách Python làm đống. Bạn cũng đã học được cách sử dụng các hoạt động cấp cao trong mô-đun Python 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5, như 
map = """\
.......X..
.......X..
....XXXX..
..........
..........
"""
8, sử dụng một đống bên trong.heap and priority queue data structures are and what kinds of problems they’re useful in solving. You learned how to use the Python 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 module to use Python lists as heaps. You also learned how to use the high-level operations in the Python 
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5 module, like 
map = """\
.......X..
.......X..
....XXXX..
..........
..........
"""
8, which use a heap internally.

Trong hướng dẫn này, bạn đã học được cách:

  • Sử dụng các chức năng cấp thấp trong mô-đun Python 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    5 để giải quyết các vấn đề cần một đống hoặc hàng đợi ưu tiênlow-level functions in the Python 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    5 module to solve problems that need a heap or a priority queue
  • Sử dụng các chức năng cấp cao trong mô-đun Python 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    5 để hợp nhất các vòng lặp được sắp xếp hoặc tìm các yếu tố lớn nhất hoặc nhỏ nhất trong mộthigh-level functions in the Python 
    >>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
    5 module for merging sorted iterables or finding the largest or smallest elements in an iterable
  • Nhận ra các vấn đề mà hàng loạt và hàng đợi ưu tiên có thể giúp giải quyếtproblems that heaps and priority queues can help solve
  • Dự đoán hiệu suất của mã sử dụng đốngperformance of code that uses heaps

Với kiến ​​thức của bạn về đống và mô -đun Python 

>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
5, giờ đây bạn có thể giải quyết nhiều vấn đề trong đó giải pháp phụ thuộc vào việc tìm ra yếu tố nhỏ nhất hoặc lớn nhất. Để làm theo cùng với các ví dụ bạn đã thấy trong hướng dẫn này, bạn có thể tải xuống mã nguồn từ liên kết bên dưới:

HEAPQ được thực hiện như thế nào trong Python?

Hàng đợi Heap là một cấu trúc cây đặc biệt trong đó mỗi nút cha nhỏ hơn hoặc bằng nút con của nó. Trong Python, nó được triển khai bằng mô -đun FEAPQ. Nó rất hữu ích là triển khai hàng đợi ưu tiên trong đó mục hàng đợi có trọng lượng cao hơn được ưu tiên hơn trong xử lý.using the heapq module. It is very useful is implementing priority queues where the queue item with higher weight is given more priority in processing.

Heapq có nghĩa là gì trong Python?

Mã nguồn: lib/heapq.py.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ó.

Nhập khẩu Heapq làm gì trong Python?

Mô -đun Python Heapq là một phần của thư viện tiêu chuẩn.Nó thực hiện tất cả các hoạt động Heap cấp thấp cũng như một số cách sử dụng phổ biến cấp cao cho đống.Hàng đợi ưu tiên là một công cụ mạnh mẽ có thể giải quyết các vấn đề khác nhau như viết một trình lập lịch email, tìm đường dẫn ngắn nhất trên bản đồ hoặc hợp nhất các tệp nhật ký.implements all the low-level heap operations as well as some high-level common uses for heaps. A priority queue is a powerful tool that can solve problems as varied as writing an email scheduler, finding the shortest path on a map, or merging log files.

Heapq sắp xếp như thế nào?

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ột đống là cấu trúc dữ liệu giống như cây nơi các nút trẻ có mối quan hệ đặt hàng với cha mẹ.implements a min-heap sort algorithm suitable for use with Python's lists. A heap is a tree-like data structure where the child nodes have a sort-order relationship with the parents.

programming python Heapq Heapq Python Priority queue Python Max heap Python Heap in C++ Heapq custom comparator Heapq find element

Bài Viết Liên Quan

Hướng dẫn what does import abc do in python? - Nhập abc làm gì trong python?
Hướng dẫn what does import abc do in python? - Nhập abc làm gì trong python?

Các gói cước mobifone 2023
Các gói cước mobifone 2023

Hướng dẫn event listener in php - trình nghe sự kiện trong php
Hướng dẫn event listener in php - trình nghe sự kiện trong php

Hướng dẫn how is print different in python 3? - in khác nhau như thế nào trong python 3?
Hướng dẫn how is print different in python 3? - in khác nhau như thế nào trong python 3?

Hướng dẫn how do you delete a text file in python? - làm thế nào để bạn xóa một tệp văn bản trong python?
Hướng dẫn how do you delete a text file in python? - làm thế nào để bạn xóa một tệp văn bản trong python?

Hướng dẫn how do i change the date format in a dataframe in python? - làm cách nào để thay đổi định dạng ngày trong khung dữ liệu trong python?
Hướng dẫn how do i change the date format in a dataframe in python? - làm cách nào để thay đổi định dạng ngày trong khung dữ liệu trong python?

Hướng dẫn python mixin best practices - các phương pháp hay nhất về python mixin
Hướng dẫn python mixin best practices - các phương pháp hay nhất về python mixin

Hướng dẫn is python a real programming language - python có phải là ngôn ngữ lập trình thực sự không
Hướng dẫn is python a real programming language - python có phải là ngôn ngữ lập trình thực sự không

File hệ thống linux
File hệ thống linux

Hướng dẫn is map used for object in javascript? - bản đồ có được sử dụng cho đối tượng trong javascript không?
Hướng dẫn is map used for object in javascript? - bản đồ có được sử dụng cho đối tượng trong javascript không?

MỚI CẬP NHẬP

Vào goole mà bị báo lỗi kết nối bảo mật năm 2024
17 phúts trước . bởi FeasibleAdvice
Ghi tờ khai thế nào khi chưa có việc làm năm 2024
33 phúts trước . bởi RollingDeflation
Duự án xây dduwngjchung cư cao cấp thuộc nhóm nào năm 2024
56 phúts trước . bởi FemaleConsistency
Trung tâm anh ngữ sài gòn vina bình dương năm 2024
1 giờs trước . bởi HaggardMouthpiece
Làm thế nào để tỉnh ngủ khi học năm 2024
1 giờs trước . bởi BorrowedNetworking
Bài tập trắc nghiệm về vecto có đáp án năm 2024
2 giờs trước . bởi Surface-to-airLaborer
Các bài toán về chứng minh của lớp 6 năm 2024
2 giờs trước . bởi CoarseFrequency
Lỗi không tạo được chữ ký trong outlook 2023 năm 2024
2 giờs trước . bởi ResplendentDiscovery
Đề thi môn toán 7 học kì 1 năm 2024
3 giờs trước . bởi UnderstandableRefinery
Cach su dung thuốc trừ sâu vào lúc nào năm 2024
4 giờs trước . bởi MonogamousDentist

Xem Nhiều

File kẹp tài liệu đục lỗ tiếng anh là gì năm 2024
6 ngàys trước . bởi InsidiousReceptor
Lỗi khi mở folder màn hình view bị thu nhỏ năm 2024
1 tuầns trước . bởi RegimentalAdoption
Viết bài văn nghị luận về bảo vệ môi trường năm 2024
5 ngàys trước . bởi RaspingPatchwork
Công văn sở giáo dục đào tạo tỉnh quảng ngãi năm 2024
4 ngàys trước . bởi DapperFoothold
Uống vitamin d vào lúc nào tốt nhất năm 2024
6 ngàys trước . bởi PrimordialHacker
Bài 35 sách giáo khoa toán 8 tập 1 năm 2024
3 ngàys trước . bởi TenuousScenery
Lỗi không gõ được tiếng việt trên amis năm 2024
4 ngàys trước . bởi PonderousCivility
Những bài toán lớp 1 giúp trẻ tư duy năm 2024
5 ngàys trước . bởi AnnoyedWomanhood
Uống omega 3 6 9 vào lúc nào năm 2024
3 ngàys trước . bởi HomogeneousLiner
Top 100 doanh nghiệp uy tính châu á năm 2024
2 ngàys trước . bởi NationwideForefront

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội

Bản quyền © 2024 Inc.