Con trăn heapq

Question

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ó. Khi đó nó được gọi là Min Heap. Nếu mỗi nút cha lớn hơn hoặc bằng nút con của nó thì nó được gọi là max heap. Sẽ rất hữu ích khi triển khai các hàng đợi ưu tiên trong đó mục hàng đợi có trọng số cao hơn được ưu tiên hơn trong quá trình xử lý

Một cuộc thảo luận chi tiết về đống có sẵn trên trang web của chúng tôi ở đây. Vui lòng nghiên cứu nó trước nếu bạn chưa quen với cấu trúc dữ liệu heap. Trong chương này, chúng ta sẽ thấy việc triển khai cấu trúc dữ liệu heap bằng python

Tạo một đống

Một đống được tạo bằng cách sử dụng thư viện có sẵn của python có tên là heapq. Thư viện này có các chức năng liên quan để thực hiện các thao tác khác nhau trên cấu trúc dữ liệu heap. Dưới đây là danh sách các chức năng này

heapify - Chức năng này chuyển đổi một danh sách thông thường thành một đống. Trong heap kết quả, phần tử nhỏ nhất được đẩy đến vị trí chỉ số 0. Nhưng phần còn lại của các phần tử dữ liệu không nhất thiết phải được sắp xếp
heappush − Chức năng này thêm một phần tử vào heap mà không làm thay đổi heap hiện tại
heappop − Hàm này trả về phần tử dữ liệu nhỏ nhất từ heap
heapreplace − Hàm này thay thế phần tử dữ liệu nhỏ nhất bằng một giá trị mới được cung cấp trong hàm

Tạo một đống

Một đống được tạo bằng cách sử dụng danh sách các phần tử có chức năng heapify. Trong ví dụ dưới đây, chúng tôi cung cấp một danh sách các phần tử và hàm heapify sắp xếp lại các phần tử đưa phần tử nhỏ nhất lên vị trí đầu tiên

Ví dụ

import heapq

H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

đầu ra

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau -

[1, 3, 5, 78, 21, 45]

Chèn vào đống

Chèn một phần tử dữ liệu vào một đống luôn thêm phần tử vào chỉ mục cuối cùng. Nhưng bạn có thể áp dụng lại hàm heapify để đưa phần tử mới được thêm vào chỉ mục đầu tiên nếu nó có giá trị nhỏ nhất. Trong ví dụ dưới đây, chúng tôi chèn số 8

Ví dụ

import heapq

H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)

# Add element
heapq.heappush(H,8)
print(H)

đầu ra

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau -

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

Xóa khỏi đống

Bạn có thể xóa phần tử ở chỉ mục đầu tiên bằng cách sử dụng chức năng này. Trong ví dụ dưới đây, hàm sẽ luôn xóa phần tử ở vị trí chỉ mục 1

Ví dụ

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Remove element from the heap
heapq.heappop(H)

print(H)

đầu ra

Khi đoạn mã trên được thực thi, nó tạo ra kết quả sau -

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

Thay thế trong một đống

Hàm thay thế heap luôn loại bỏ phần tử nhỏ nhất của heap và chèn phần tử mới đến vào một vị trí không cố định theo bất kỳ thứ tự nào

Hàng đống và hàng đợi ưu tiên là những cấu trúc dữ liệu ít được biết đến nhưng hữu ích một cách đáng ngạc nhiên. Đối với nhiều vấn đề liên quan đến việc tìm kiếm phần tử tốt nhất trong tập dữ liệu, họ đưa ra 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]

6 là một phần của thư viện 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 heap

A là một công cụ mạnh mẽ có thể giải quyết các vấn đề đa dạng như viết trình lập lịch trình email, tìm đường đi 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 chứa đầy các vấn đề tối ưu hóa, trong đó mục tiêu là tìm ra phần tử tốt nhất. Hàng đợi ưu tiên và các chức năng trong mô-đun

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

6 của Python thường có thể giúp ích cho việc đó

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

Đống và hàng đợi ưu tiên là gì và chúng liên quan với nhau như thế nào
Những loại vấn đề nào có thể được giải quyết bằng cách sử dụng một đố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]

6 để giải quyết những vấn đề đó

Hướng dẫn này dành cho Pythonistas, những người cảm thấy thoải mái với danh sách, ký tự, bộ và trình tạo và đang tìm kiếm các cấu trúc dữ liệu phức tạp hơn

Bạn có thể làm theo 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

Lấy mã nguồn. Nhấp vào đây để lấy mã nguồn mà bạn sẽ sử dụng để tìm hiểu về mô-đun heapq Python trong hướng dẫn này

đống là gì?

Đố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. 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

Heap thường được sử dụng để triển khai hàng đợi ưu tiên. Chúng là cấu trúc dữ liệu cụ thể phổ biến nhất để triển khai 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 xác định đảm bảo hiệu suất. Đảm bảo hiệu suất xác định mối quan hệ giữa kích thước của cấu trúc và thời gian thực hiện các hoạt động. 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 đầu vào của nó thay đổi

Loại bỏ các quảng cáo

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 chỉ đị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 của hàng đợi ưu tiên hỗ trợ ba thao tác

is_empty kiểm tra xem hàng đợi có trống không
add_element thêm một phần tử vào hàng đợi
pop_element bật phần tử có mức ưu tiên cao nhất

Hàng đợi ưu tiên thường được sử dụng để tối ưu hóa việc thực thi tác vụ, trong đó mục tiêu là thực hiện tác vụ có 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ó sẽ bị hạ xuống và nó được đưa 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 phần tử

Phần tử lớn nhất có mức ưu tiên cao nhất
Phần tử nhỏ nhất có mức ưu tiên cao nhất

Hai quy ước này tương đương nhau vì bạn luôn có thể đảo ngược thứ tự thực tế. Ví dụ: nếu các phần tử của bạn bao gồm các số, thì việc sử dụng số âm sẽ đảo ngược 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]

6 sử dụng quy ước thứ hai, thường là quy ước phổ biến hơn trong hai quy ước. Theo quy ước này, phần 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 này, quy ước này sẽ đơn giản hóa mã của bạn

Ghi chú. Mô-đun Python

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

6 và cấu trúc dữ liệu heap nói chung không được thiết kế để cho phép tìm bất kỳ phần tử nào ngoại trừ phần tử nhỏ nhất. Để truy xuất bất kỳ phần tử nào theo kích thước, tùy chọn tốt hơn là cây tìm kiếm nhị phâ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 các đả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à bật (xóa) đều là 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 thao tác đẩy và bật tỷ lệ thuận với logarit cơ số 2 của số phần tử

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 phần tử, thì nó sẽ chỉ chậm hơn mười lần trên một nghìn tỷ phần tử và có thể vẫn đủ nhanh

Trong bất kỳ cuộc thảo luận nào về hiệu suất, lưu ý 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 việc đo lường thực sự một chương trình cụ thể và tìm hiểu xem các nút thắt cổ chai nằm ở đâu. Đảm bảo hiệu suất chung vẫn rất quan trọng để đưa ra các 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

Heap cài đặt hàng đợi ưu tiên dưới dạng cây nhị phân hoàn chỉnh. Trong cây nhị phân, mỗi nút sẽ có nhiều nhất hai nút con. Trong một cây nhị phân hoàn chỉnh, tất cả các mức trừ mức sâu nhất có thể 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 về bên trái càng tốt

Thuộc tính đầy đủ có nghĩa là độ sâu của cây là logarit cơ số 2 của số phần tử, được làm tròn lên. Đây là một ví dụ về cây nhị phân hoàn chỉnh

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ừ nút sâu nhất có đúng hai nút con. Có tổng cộng bảy nút ở ba cấp độ. Ba là logarit cơ số 2 của bảy, được làm tròn lên

Nút duy nhất ở cấp cơ sở được gọi là nút gốc. Có vẻ lạ khi gọi nút ở trên cùng của 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

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

Ghi chú. So sánh đôi khi liên quan đến việc gọi mã do người dùng xác định bằng cách sử dụng

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

1. Gọi các phương thức do người dùng định nghĩa trong Python là một thao tác tương đối chậm so với các thao tác khác được thực hiện trong một đống, vì vậy đây thường sẽ là nút cổ chai

Trong cây heap, giá trị trong một nút luôn nhỏ hơn cả hai nút 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 nút cha của nó

Các thuật toán cho cả push và popping dựa vào việc tạm thời vi phạm thuộc tính heap, sau đó sửa thuộc tính heap thông qua 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 sẽ thêm nút mới vào vị trí mở tiếp theo. Nếu lớp dưới cùng không đầy, thì nút đó sẽ được thêm vào vị trí mở tiếp theo ở dưới cùng. 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 sẽ so sánh nút đó với nút gốc của nó. Nếu thuộc tính heap bị vi phạm, thì nút và cha của nó sẽ được chuyển đổi và quá trình kiểm tra bắt đầu lại tại cha. Điều này tiếp tục cho đến khi thuộc tính heap được giữ hoặc đã đạt đến gốc

Tương tự, khi popping phần tử nhỏ nhất, Python biết rằng, do thuộc tính heap, phần tử nằm ở gốc của 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 ở nhánh không

Loại bỏ các quảng cáo

Công dụng của hàng đợi ưu tiên

Hàng đợi ưu tiên và heap dưới dạng triển khai 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 phần tử cực trị 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ỳ tác vụ nào sau đây

Lấy ba bài đăng blog phổ biến nhất từ dữ liệu lượt truy cập
Tìm cách nhanh nhất để đi từ điểm này đến điểm khác
Dự đoán xe buýt nào sẽ đến ga đầu tiên dựa trên tần suất đế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 gửi email. Hãy tưởng tượng một hệ thống có nhiều loại email, mỗi loại cần được gửi ở một tần suất nhất định. Một loại email cần được gửi đi cứ sau mười lăm phút và một loại khác cần được gửi sau mỗi bốn mươi phút

Người lên 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 nào cần gửi email tiếp theo. Sau đó, bộ lập lịch có thể xem phần tử có dấu thời gian nhỏ nhất—cho biết phần tử đó sẽ được gửi tiếp theo—và tính toán thời gian ngủ trước khi gửi

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

Đống dưới dạng Danh sách trong Mô-đun >>> import heapq >>> a = [3, 5, 1, 2, 6, 8, 7] >>> heapq.heapify(a) >>> a [1, 2, 3, 5, 6, 8, 7] 6 của Python

Mặc dù bạn đã thấy heap đượ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à luôn có thể biết có bao nhiêu phần tử ở mỗi lớp ngoại trừ lớp cuối cùng. Do đó, đống có thể được triển khai dưới dạng 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]

6 làm

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

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

4 và các phần tử xung quanh nó

Đứa con đầu lòng của nó là vào lúc

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

5

Đứa con thứ hai của nó là lúc

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

6

Cha mẹ của nó là tại

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

7

Ghi chú. Ký hiệu

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

8 là toán tử chia số nguyên. Nó luôn làm tròn xuống một số nguyên

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

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

9 nằm ngoài cuối danh sách, thì phần tử không có phần tử con nào. Nếu

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

5 là một chỉ mục 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]

6 thì không, thì phần tử chỉ có một con

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

>>> 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

2 là một đống thì phần sau sẽ không bao giờ là

>>> 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

3

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

4 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 = [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

3

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ủa nó cộng một và hai lần chỉ số của nó cộng hai

Đây là hình ảnh của một danh sách thỏa mãn thuộc tính heap

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]

4 đến phần tử

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

5 và

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

6. Ví dụ: phần tử đầu tiên trong danh sách Python 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

9, vì vậy hai mũi tên của nó chỉ vào các chỉ số

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)

0 và

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. Lưu ý cách các mũi tên luôn đi từ giá trị nhỏ hơn đến 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]

6 thực hiện các thao tác heap trên danh sách. Không giống như nhiều mô-đun khác, nó không định nghĩa 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]

6 có các chức năng hoạt động trực tiếp trên danh sách

Thông thường, như trong ví dụ email ở trên, các phần tử sẽ được chèn từng phần tử một vào heap, bắt đầu bằng một heap trống. Tuy nhiên, nếu đã có một danh sách các phần 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]

6 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)

5 để biến một danh sách thành một đống hợp lệ

Đoạn 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)

5 để 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)

7 thành một đống

>>>

>>> 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)

8 đứng 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)

9 nhưng 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)

7 vẫn tuân theo thuộc tính heap. Ví dụ:

>>> 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')

1, là

>>> 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')

2, nhỏ hơ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')

3, 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ư 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)

5 sửa đổi danh sách tại chỗ nhưng không sắp xếp nó. Một đống không cần phải được sắp xếp để đáp ứng thuộc tính 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, nên việc 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)

5 trên danh sách được sắp xếp sẽ không thay đổi thứ tự của các phần 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]

6 giả định rằng danh sách đã là một đống. Thật hữu ích khi lưu ý rằng một danh sách trống hoặc danh sách có độ dài sẽ luôn là một đống

Vì gốc của cây là phần tử đầu tiên, nên bạn không cần một chức năng chuyên dụng để đọc phần tử nhỏ nhất một cách 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')

8, sẽ luôn là phần tử nhỏ nhất

Để bật phần tử nhỏ nhất trong khi vẫn giữ nguyê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]

6 định nghĩa

>>> 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

Đây là 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

0 để bật mộ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]

Hàm trả về phần tử đầu tiê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)

0 và giữ nguyê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)

7. 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

4 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

5 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

6 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

7

Mô-đun Python

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

6 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

9 để đẩy một phần tử vào heap trong khi vẫn giữ nguyên thuộc tính heap

Ví dụ sau đây cho thấy việc đẩy một giá trị lên mộ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

Sau khi đẩy

import heapq

0 vào đống, bạn bật ba phần tử từ nó. Vì

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 và

>>> 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')

2 đã ở trong đống và nhỏ hơn

import heapq

0 nên chúng được xuất hiện đầu tiê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]

6 cũng định nghĩa thêm hai thao tác

import heapq

5 tương đương với

>>> 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 theo sau bởi

>>> 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

9

import heapq

8 tương đương với

>>> 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

9 theo sau bởi

>>> 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

Chúng hữu ích trong một số thuật toán vì chúng hiệu quả hơn so với thực hiện hai thao tác riêng biệt

Loại bỏ các quảng cáo

Hoạt động cấp cao

Vì các hàng đợi ưu tiên thường được sử dụng để hợp nhất các chuỗi đã sắp xếp, nên mô-đun

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

6 của Python có một chức năng làm sẵn,

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

2, để sử dụng các đống để hợp nhất một số lần lặp.

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

2 giả sử các iterable đầu vào của nó đã được sắp xếp và trả về một iterator, không phải danh sách

Như một ví dụ về việc sử dụng

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

2, đây là cách triển khai bộ lập lịch email được mô tả trước đó

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)

Đầu vào cho

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

2 trong ví dụ này là. Giá trị trả về được gán cho biến

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

6 cũng là một trình vòng lặp vô hạn. Trình lặp này sẽ mang lại các email được gửi theo thứ tự dấu thời gian trong tương lai

Để gỡ lỗi và xác nhận rằng mã được hợp nhất chính xác, bạn có thể in mười email đầu tiên sẽ được gử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')

Lưu ý cách

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

7 được lên lịch mỗi

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

8 phút,

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

9 được lên lịch mỗi

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

0 và các email được xen kẽ hợp lý để chúng được sắp xếp theo thứ tự dấu thời gian của chúng

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

2 không đọc tất cả dữ liệu đầu vào, mà thay vào đó, nó hoạt động linh hoạt. Mặc dù cả hai đầu vào đều là trình lặp vô hạn, việc in mười mục đầu tiên sẽ kết thúc nhanh chóng

Theo cách tương tự, khi được sử dụng để hợp nhất các chuỗi đã sắp xếp như các dòng tệp nhật ký được sắp xếp theo dấu thời gian, ngay cả khi nhật ký lớn, điều này sẽ chiếm một lượng bộ nhớ hợp lý

đống vấn đề có thể giải quyết

Như bạn đã thấy ở trên, đống rất tốt cho việc hợp nhất dần dần các chuỗi đã sắp xếp. Hai ứng dụng cho đống mà bạn đã xem xét là lên lịch các tác vụ định kỳ và hợp nhất các tệp nhật ký. Tuy nhiên còn rất nhiều ứng dụng khác

Đống cũng có thể giúp xác định n thứ trên cùng hoặc n thứ dưới cù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]

6 có các chức năng cấp cao thực hiện hành vi này

Ví dụ: mã này lấy dữ liệu đầu vào là thời gian từ trận chung kết 100 mét nữ tại Thế vận hội Mùa hè 2016 và in ra những người đoạt huy chương hoặc ba người về đích hàng đầu

>>>

>>> 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

Mã này sử dụng

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

3 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]

6.

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

3 trả về các phần tử nhỏ nhất trong một lần lặp và chấp nhận ba đối số

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

6 cho biết có bao nhiêu phần tử cần trả về

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

7 xác định các yếu tố hoặc tập dữ liệu để so sánh

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

8 là một hàm có thể gọi được để xác định cách so sánh các phần tử

Ở đây, hàm

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

8 tách dòng theo khoảng trắng, lấy phần tử cuối cùng và chuyển đổi nó thành một. Đ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 có thời gian chạy nhỏ nhất. Những thứ này tương ứng với ba vận động viên chạy nhanh nhất, mang lại cho bạn huy chương vàng, bạc và đồng

Mô-đun

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

6 của Python cũng bao gồm

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

01, có các tham số tương tự và trả về các phần tử lớn nhất. Điều này sẽ hữu ích nếu bạn muốn giành huy chương từ cuộc thi ném lao, trong đó mục tiêu là ném lao càng xa càng tốt

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

Một đống, với tư cách là một triển khai của 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 điểm cực đoan, chẳng hạn như nhiều 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
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 yếu tố cực đoan nào đó, bạn nên suy nghĩ xem hàng đợi ưu tiên có 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ể của lập trình động. Đây là trường hợp của 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 cùng nhau

Loại bỏ các quảng cáo

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]

6. Ví dụ này sẽ sử dụng một thuật toán cổ điển, là một phần của nó, yêu cầu 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

Lấy mã nguồn. Nhấp vào đây để lấy mã nguồn mà bạn sẽ sử dụng để tìm hiểu về mô-đun heapq Python trong hướng dẫn này

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 đi từ điểm xuất phát, nằm ở góc trên cùng bên trái, đến điểm đến ở góc dưới cùng bên phải. Robot có một bản đồ mê cung trong bộ nhớ, vì vậy nó có thể vạch ra toàn bộ đường đi trước khi khởi hành

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

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

```
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
```
03 là bản đồ đường đi dự kiến từ điểm gốc đến vị trí,
```
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
```
04. Con đường được gọi là dự kiến vì nó là con đường ngắn nhất đã biết, nhưng nó có thể được cải thiện khi

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

05 là tập hợp các điểm mà đường đi mà

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

03 ánh xạ chắc chắn là đường đi ngắn nhất có thể

```
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
```
07 là một đống vị trí có đường dẫn. Khóa sắp xếp của heap là độ dài của đường dẫn

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

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]

07

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]

05. Nếu ứng viên đã là thành viên của nhóm

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

05, thì bỏ qua hai hành động tiếp theo

Tìm đường đi ngắn nhất đã biết đến ứng viên hiện tại

Đối với mỗi hàng xóm trực tiếp của ứng viên hiện tại, hãy xem liệu việc đi qua ứng viên có cung cấp một con đường ngắn hơn con đường

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

03 hiện tại hay không. Nếu vậy, hãy cập nhật đường dẫn

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

03 và đống

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

07 bằng đườ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]

05. Khi điểm đến nằm trong tập hợp

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

05, bạn đã hoàn thành. Đầu ra của thuật toán là đường dẫn

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

03 đến đích, bây giờ là đường dẫn ngắn nhất có thể là ____6_______05

Mã cấp cao nhất

Bây giờ bạn đã hiểu thuật toán, đã đến lúc viết mã để triển khai nó. Trước khi tự triển khai thuật toán, bạn nên viết một số mã hỗ trợ

Trước tiên, bạn cần đế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]

6

import heapq

Bạn sẽ sử dụng các hàm từ mô-đun

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

6 của Python để duy trì một đống giúp bạn tìm vị trí có đường đi ngắn nhất đã biết ở mỗi lần lặp

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

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

Bản đồ là một bản đồ hiển thị 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ẽ yêu cầu bạn đọc bản đồ từ một tệp, nhưng vì mục đích giảng dạy, việc xác định một biến trong mã bằng cách sử dụng bản đồ đơn giản này sẽ dễ dàng hơn. Mã này sẽ hoạt động trên mọi bản đồ nhưng sẽ dễ hiểu và dễ gỡ lỗi hơn trên bản đồ đơn giản

Bản đồ này được tối ưu hóa để dễ hiểu đối với người đọc mã của con người. Dấu chấm (_______6_______20) đủ sáng để trông có vẻ trống rỗng, nhưng nó có lợi thế là hiển thị kích thước của khu vực được phép. Các vị trí

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

21 đánh dấu các chướng ngại vật mà robot không thể đi qua

Loại bỏ các quảng cáo

Mã hỗ trợ

Chức năng đầu tiên sẽ chuyển đổi bản đồ thành thứ gì đó dễ phân tích cú pháp 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]

22 lấy 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

Hàm lấy một bản đồ và trả về một bộ gồm ba phần tử

Danh sách

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

23

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

24

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

25

Đ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 dành cho khả năng quét trực quan của con người

Danh sách

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

23 có thể được lập chỉ mục theo tọa độ

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

27. 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]

28 trả về giá trị của vị trí là một trong hai ký tự

Dấu chấm (_______6_______29) cho biết vị trí là một khoảng trống

Chữ cái

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

30 chỉ vị trí là chướng ngại vật

Điều này sẽ hữu ích khi bạn muốn tìm những 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]

31 tính toán xem 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]

27 đã cho có hợp lệ hay không

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

0

Hàm này nhận hai đối số

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

23 là bản đồ dưới dạng danh sách các đường

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

34 là vị trí cần kiểm tra dưới dạng hai bộ số nguyên biểu thị tọa độ

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

27

Để hợp lệ, một vị trí phải nằm trong ranh giới của bản đồ và không phải là chướng ngại vật

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]

36 có hợp lệ hay không 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]

23. Hàm tiếp theo sẽ 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]

38 có hợp lệ hay không bằng cách đảm bảo rằng nó nằm bên trong

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

39. Cuối cùng, bây giờ bạn đã biết cả hai tọa độ đều nằm trong bản đồ, mã sẽ kiểm tra xem chúng có phải là chướng ngại vật hay không bằng cách nhìn vào ký 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]

30

Một công cụ 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]

41, tìm tất cả các lân cận 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]

1

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]

41 cẩn thận để tránh xác định một vị trí là hàng xóm của chính nó, nhưng nó cho phép các 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]

43 và

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

44 không được bằng 0, nhưng cả hai khác không cũng không sao

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]

45, tìm 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]

2

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

45 mang lại các vị trí mà đường dẫn có ____6_______47 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]

45 có ba tham số

>>> 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 từ điển ánh xạ một vị trí tới con đường ngắn nhất đã biết

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

50 là một vị trí có thể lặp lại mà bạn muốn rút ngắn đường đi

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

47 là vị trí mà qua đó, có lẽ, có thể tìm thấy 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]

50

Giả định là tất cả các phần tử trong

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

50 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]

47

Hàm

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

45 kiểm tra xem việc sử dụng

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

47 làm bước cuối cùng có tạo ra một đường dẫn tốt hơn cho từng vị trí hay không. Nếu không biết đườ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ỉ tạo ra đường dẫn mới nế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]

45 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]

58 cũng là con đường ngắn hơn

Tất cả các hàm của trình trợ giúp được viết là các hàm thuần túy, 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 dễ dàng tuân theo thuật toán cốt lõi, thuật toán này thực hiện tất cả các cập nhật cấu trúc dữ liệu

Loại bỏ các quảng cáo

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

Tóm lại, bạn đang tìm kiếm con đường ngắn nhất giữa điểm xuất phát và điểm đến

Bạn giữ ba mẩu dữ liệu

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

05 là tập hợp các vị trí nhất định

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

07 là đống ứng cử viên

>>> 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 nút ánh xạ từ điển tới đường dẫn ngắn nhất đã biết hiện tại

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]

05 nếu bạn có thể chắc chắn rằng con đường ngắn nhất đã biết là con đường ngắn nhất có thể. Nếu điểm đến nằm trong tập hợp

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

05, thì đường đi ngắn nhất đã biết đến đích chắc chắn là đường đi ngắn nhất có thể và bạn có thể trả về đường đi này

Đống

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

07 được sắp xếp theo độ dài của đường đi ngắn nhất đã biết và được quản lý với sự trợ giúp của các hàm trong mô-đun

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

6 của Python

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

>>> 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. Không có con đường nào ngắn hơn đến ứng cử viên này—tất cả các con đường khác đều đ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]

07 và tất cả những con đường này đều dài hơn. Do đó, ứng viên hiện tại có thể được đánh dấu là

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

05

Sau đó, bạn xem xét tất cả các hàng xóm chưa được thăm và nếu việc đ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]

07 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

9

Hàm

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

71 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]

3

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

71 nhận một

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

73 dưới dạng một chuỗi và trả về đường dẫn từ điểm 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 xem qua từng chút một

Các dòng từ 2 đến 5 thiết lập các biến mà vòng lặp sẽ xem xét và cập nhật. Bạn đã biết một đường đi từ gốc tọa độ đến chính nó, đó là đường đi trống, độ dài 0

Dòng 6 xác định điều kiện kết thúc của 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]

07 thì không thể rút ngắn đường đi. Nếu

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

25 nằm trong

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

05, thì không thể rút ngắn đườ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]

25

Các dòng từ 7 đến 10 lấy ứng viên 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

0, bỏ qua vòng lặp nếu nó đã có trong

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

05 và nếu không thì thêm ứng 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]

05. Đ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

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]

41 và

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

45 để 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 đống từ điển

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

03 và đống

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

07

Các dòng 16 đến 19 giải quyết 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ả về nó. Mặc dù việc tính toán các đường dẫn không có vị trí cuối cùng giúp việc triển khai thuật toán trở nên đơn giản hơn, nhưng đó là một API đẹp hơn để trả về nó cùng với đích. Nếu không tìm thấy đường dẫn, thì một ngoại lệ được đưa ra

Chia chức năng thành các phần riêng biệt cho phép bạn hiểu từng phần một

Mã trực quan

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

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

85 vẽ một con đường 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]

4

Hàm lấy các tham số là

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

86 và

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

73. Nó trả về một bản đồ mới với đường dẫn được biểu thị bằng ký hiệu at (

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

88)

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ừ

Đoạn mã sau sẽ chạy thuật toán và hiển thị một đầu ra đẹp

>>>

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

5

Trước tiên, bạn có được con đường ngắn nhất từ _______6_______71. Sau đó, bạn chuyển nó cho

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

85 để hiển thị bản đồ với đường dẫn được đánh dấu trê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]

91 ánh xạ ra chuẩn đầu ra

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

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]

6

Những loại vấn đề tìm đường này, có thể giải quyết được bằng cách kết hợp lập trình động và hàng đợi ưu tiên, thường gặp trong các cuộc phỏng vấn xin việc và thử thách lập trình. Ví dụ: Advent of Code 2019 bao gồm một vấn đề có thể được giải quyết bằng các kỹ thuật được mô tả tại đây

Loại bỏ các quảng cáo

Phần kết luận

Bây giờ bạn đã biết cấu trúc dữ liệu hàng đợi ưu tiên và heap là gì và loại vấn đề nào chúng 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]

6 để sử dụng danh sách Python dưới dạng đống. Bạn cũng đã học cách sử dụng các thao tác cấp cao trong mô-đun

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

6 của Python, chẳng hạn như

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

2, sử dụng một đống trong nội bộ

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

Sử dụng các hàm cấp thấp trong mô-đun
```
>>> import heapq
>>> a = [3, 5, 1, 2, 6, 8, 7]
>>> heapq.heapify(a)
>>> a
[1, 2, 3, 5, 6, 8, 7]
```
6 của Python để giải quyết các vấn đề cần một đống hoặc một hàng đợi ưu tiên
Sử dụng các hàm 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]
```
6 để hợp nhất các lần lặp đã sắp xếp hoặc tìm các phần tử lớn nhất hoặc nhỏ nhất trong một lần lặp
Nhận ra các vấn đề mà hàng đợi ưu tiên và đống có thể giúp giải quyết
Dự đoán hiệu suất của mã sử dụng đống

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

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

6 của Python, giờ đây bạn có thể giải nhiều bài toán trong đó lời giải phụ thuộc vào việc tìm phần tử nhỏ nhất hoặc lớn nhất. Để làm theo 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

Lấy mã nguồn. Nhấp vào đây để lấy mã nguồn mà bạn sẽ sử dụng để tìm hiểu về mô-đun heapq Python trong hướng dẫn này

Đánh dấu là đã hoàn thành

🐍 Thủ thuật Python 💌

Nhận một Thủ thuật Python ngắn và hấp dẫn được gửi đến hộp thư đến của bạn vài ngày một lần. Không có thư rác bao giờ. Hủy đăng ký bất cứ lúc nào. Được quản lý bởi nhóm Real Python

Gửi cho tôi thủ thuật Python »

Giới thiệu về Moshe Zadka

Moshe đã sử dụng Python từ năm 1998. Anh ấy đã đóng góp cho CPython và là thành viên sáng lập của dự án Twisted. Anh ấy đã dạy Python ở nhiều địa điểm khác nhau từ năm 2002

» Thông tin thêm về Moshe

Mỗi hướng dẫn tại Real Python được tạo bởi một nhóm các nhà phát triển để nó đáp ứng các tiêu chuẩn chất lượng cao của chúng tôi. Các thành viên trong nhóm đã làm việc trong hướng dẫn này là

Aldren

David

Geir Arne

Joanna

Gia-cốp

Bậc thầy Kỹ năng Python trong thế giới thực Với quyền truy cập không giới hạn vào Python thực

Tham gia với chúng tôi và có quyền truy cập vào hàng nghìn hướng dẫn, khóa học video thực hành và cộng đồng các Pythonistas chuyên gia

Nâng cao kỹ năng Python của bạn »

Chuyên gia Kỹ năng Python trong thế giới thực
Với quyền truy cập không giới hạn vào Python thực

Tham gia với chúng tôi và có quyền truy cập vào hàng ngàn hướng dẫn, khóa học video thực hành và cộng đồng Pythonistas chuyên gia

Nâng cao kỹ năng Python của bạn »

Bạn nghĩ sao?

Đánh giá bài viết này

Tweet Chia sẻ Chia sẻ Email

Bài học số 1 hoặc điều yêu thích mà bạn đã học được là gì?

Mẹo bình luận. Những nhận xét hữu ích nhất là những nhận xét được viết với mục đích học hỏi hoặc giúp đỡ các sinh viên khác. và nhận câu trả lời cho các câu hỏi phổ biến trong cổng thông tin hỗ trợ của chúng tôi

programming python

Con trăn heapq

Tạo một đống

Tạo một đống

Ví dụ

đầu ra

Chèn vào đống

Ví dụ

đầu ra

Xóa khỏi đống

Ví dụ

đầu ra

Thay thế trong một đống

đống là gì?

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

Thực hiện đống

Công dụng của hàng đợi ưu tiên

Đống dưới dạng Danh sách trong Mô-đun >>> import heapq >>> a = [3, 5, 1, 2, 6, 8, 7] >>> heapq.heapify(a) >>> a [1, 2, 3, 5, 6, 8, 7] 6 của Python

Hoạt động cơ bản

Hoạt động cấp cao

đống vấn đề có thể giải quyết

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

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

Mã cấp cao nhất

Mã hỗ trợ

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

Mã trực quan

Chạy mã

Phần kết luận

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội