Heapq triển khai hàng đợi ưu tiên trong Python như thế nào?

Đối với phân tích dữ liệu, sử dụng ngôn ngữ lập trình Python là thuận lợi và trong một số trường hợp nhất định, hiệu quả hơn các công nghệ khác. Nó cung cấp một câu trả lời đơn giản và mạnh mẽ cho nhiều vấn đề liên quan đến việc chọn phần tốt nhất trong tập dữ liệu. Cấu trúc dữ liệu ít được biết đến nhưng hữu ích đáng ngạc nhiên bao gồm hàng đợi ưu tiên và đống

Thư viện chuẩn bao gồm mô-đun heapq Python. Nó thực hiện tất cả các hoạt động của heap ở mức thấp và một số ứng dụng heap điển hình ở mức cao

Dung dịch

Sự kết hợp giữa hàng đợi ưu tiên với đống là một công cụ giải quyết vấn đề hiệu quả. Trong nhiều trường hợp, hàng đợi ưu tiên và các phương thức của mô-đun heapq trong Python có thể hữu ích

Trong hướng dẫn Python này, bạn sẽ học những điều sau

• Hàng đợi và đống ưu tiên là gì và chúng liên quan với nhau như thế nào?
• Cách sử dụng mô-đun heapq trong Python

đống là gì?

Heap là một cấu trúc dữ liệu dựa trên cây trong đó các nút của cây được sắp xếp theo một thứ tự cụ thể. Về bản chất, nó là một cây nhị phân đầy đủ tuân thủ các đặc điểm của heap như min-heap và max-heap

Heaps được sử dụng trong một số thuật toán nổi tiếng, bao gồm triển khai hàng đợi ưu tiên, thuật toán sắp xếp heap sort và phương pháp Dijkstra để xác định đường đi ngắn nhất. Đống về cơ bản là cấu trúc dữ liệu bạn sẽ sử dụng khi cần nhanh chóng truy xuất phần tử nhỏ nhất hoặc lớn nhất. Dưới đây là một ví dụ về Biểu diễn cây và Biểu diễn mảng

đại diện cây

Biểu diễn mảng

Thông tin có thể được hiển thị dưới dạng một mảng các khóa, từ đó có thể suy ra vị trí của trẻ bên trái và bên phải bằng cách sử dụng kết nối toán học đơn giản. Nếu một phần tử của chỉ số k được đưa ra

• chỉ số con trái. 2*k + 1
• chỉ mục con. 2*k + 2
• chỉ mục gốc. k /2 (lấy sàn)

Chúng tôi có hai loại heap trong Python

1. Min_Heap. Phần tử cha là nhỏ nhất trong số các phần tử con bên trái và bên phải của nó và phần tử gốc là phần tử nhỏ nhất trong tất cả các phần tử
2. Max_Heap. Phần tử cha là phần tử lớn nhất trong số các phần tử con bên trái và bên phải của nó và phần tử gốc là phần tử lớn nhất trong tất cả các phần tử

Cây nhị phân thường được sử dụng để thực hiện heap. Chúng được tổ chức sao cho chúng ta có thể truy cập nhanh chóng và liên tục vào phần tử tối thiểu của chỉ mục đầu tiên. Phần còn lại của cây/đống không phải lúc nào cũng được sắp xếp. Chúng tôi có thể xử lý một đống dưới dạng danh sách bằng mô-đun heapq trong Python

ví dụ

Hãy lấy đầu vào là [6,8,9,2,4]. Sắp xếp đầu vào bằng cấu trúc cây

Min-Heap. Quy tắc "Nút cha phải nhỏ hơn hoặc bằng nút con" áp dụng cho Min-heap

Trong đầu vào này, nút cha "6" đáp ứng yêu cầu vì "8 và 9" là con của nút cha. Mặc dù "2 và 4" là nút cha của "8", nhưng nút cha 8 không đáp ứng yêu cầu. Do đó, 8 và 2 phải được chuyển đổi, như minh họa trong Img 1

Nút cha "6" không đáp ứng yêu cầu; . Do đó, 6 và 2 phải được chuyển đổi, như thể hiện trong Img 2

Nút cha "6" không đáp ứng yêu cầu và "8 và 4" là nút con của nút cha. Kết quả là, 6 và 4 phải được chuyển đổi, như thể hiện trong Img 3

Trong Hình 3, "4 và 9" là nút con của nút cha "2", thỏa mãn tiêu chí. "8 và 6" là nút con của nút cha "4", đáp ứng yêu cầu. Sau đó, chúng tôi đã tạo cấu trúc min-heap

Heap tối thiểu đầu ra là [2,4,9,8,6] cho đầu vào [6,8,9,2,4]

Heap tối đa. Quy tắc "Nút cha phải lớn hơn hoặc bằng nút con" áp dụng cho Max-heap

Img 4 mô tả "8 và 9" là nút con của nút cha có tên là "6", nhưng vì nút cha 6 không đáp ứng tiêu chí nên chúng tôi phải hoán đổi 6 và 9, như minh họa trong Img 5

Img 5 cho thấy "8 và 6" là nút con của nút cha "9" đáp ứng tiêu chí và "2 và 4" là nút con của nút cha "8" cũng đáp ứng tiêu chí. Sau đó, chúng tôi đã tạo cấu trúc max-heap

Heap tối đa đầu ra là [2,4,9,8,6] cho đầu vào [9,8,6,2,4]

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

Hàng đợi được sắp xếp theo một thuộc tính của các mục trong hàng đợi được gọi là hàng đợi ưu tiên. Hàng đợi ưu tiên có ba đặc điểm bổ sung trên hàng đợi

1. Có một "mức độ ưu tiên" được gán cho từng phần tử
2. Mức độ ưu tiên xác định phần tử nào được bật lên trước. các yếu tố ưu tiên cao hơn được xuất hiện đầu tiên
3. Khi hai phần tử có cùng mức độ ưu tiên, thứ tự mà chúng được thêm vào hàng đợi sẽ xác định cách chúng được phục vụ (xuất hiện)

Heap và hàng đợi ưu tiên liên quan như thế nào?

Việc triển khai heap của hàng đợi ưu tiên đảm bảo rằng cả việc thêm và xóa các mục nhập đều mất một lượng thời gian logarit. Do đó, thời gian cần thiết để thực hiện thao tác đẩy và bật có liên quan tỷ lệ thuận với logarit cơ số 2 của số phần tử

Thực hiện chức năng Heapq

Để triển khai cấu trúc dữ liệu heap trong Python, hãy sử dụng mô-đun heapq. Mô-đun này chủ yếu minh họa loại min-heap. Không có khái niệm max-heap trong mô-đun heapq trong Python

Bước 1. heapify (đầu vào)

Danh sách đầu vào được thay đổi thành cấu trúc dữ liệu min-heap bằng cách sử dụng nó

import heapq
input = [4,6,2,8,1,5]
heapq.heapify(input)
print("heap is")
print(input)

• Nhập mô-đun heapq
• Bây giờ lấy đầu vào là [4,6,2,8,1]
• Cấu trúc min-heap được tạo bằng hàm heapify

đầu ra

Bước 2. heappush(đầu vào, phần tử)

Nó được sử dụng để duy trì cấu trúc heap và đặt phần tử vào heap

import heapq
input = [4,6,2,8,1,5]
heapq.heappush(input,10)
print("heap after push the element 10")
print(input)

• Cấu trúc heap sẽ là [4,6,2,8,1,5]
• Sử dụng hàm heappush để thêm phần tử "10" vào cấu trúc heap

đầu ra

Bước 3. heappop(đầu vào)

Nó được sử dụng để duy trì cấu trúc heap và loại bỏ mảnh nhỏ nhất khỏi heap

import heapq
input = [6,2,8,1,5]
heapq.heapify(input)
print("after heapify the heap is")
print(input)
print("smallest element in heap is")
print(heapq.heappop(input))

• Cấu trúc heap sẽ là [6,2,8,1,5]
• Sử dụng chức năng hepify, hepify đầu vào và tạo một đống nhỏ
• Chúng ta có thể loại bỏ phần tử nhỏ nhất khỏi heap bằng cách sử dụng heappop

đầu ra

Phần tử nhỏ nhất và đầu tiên trong heap là 1

Bước 4. heappushpop(đầu vào, phần tử)

Chức năng này đại diện cho sự kết hợp của chức năng đẩy và bật. Phần tử được cung cấp được đẩy lên trước, tiếp theo là phần tử nhỏ nhất

import heapq
input = [3,4,6,1,4,7]
heapq.heapify(input)
print("The popped item using heappop")
print(heapq.heappop(input))

• Lấy đầu vào là [3,4,6,1,4,7]
• Cấu trúc heap tối thiểu được tạo bằng đầu vào của hàm heapify [1, 3, 6, 4, 4, 7]
• Hàm Heappushpop mở rộng cấu trúc heap bằng cách thêm phần tử "2" và loại bỏ phần tử nhỏ nhất

đầu ra

Bước 5. heapreplace(đầu vào, phần tử)

Hàm này cũng thêm và xóa các phần tử, nhưng nó thực hiện theo một cách khác với heappushpop. Phần tử nhỏ nhất ban đầu được xuất hiện trong heapreplace này, sau đó phần tử được đẩy

import heapq
input = [3,4,6,4,7]
heapq.heapify(input)
print("The poppes iteam using heapreplace")
print(heapq.heapreplace(input,2))

• Lấy đầu vào là [3,4,6,4,7]
• Cấu trúc heap tối thiểu được tạo bằng cách sử dụng đầu vào của hàm heapify [3, 6, 4, 4, 7]
• Phương thức Heapreplace loại bỏ phần tử nhỏ nhất, "2," trước khi thêm phần tử mới, "2. " Phần tử pop, trong trường hợp này, là "3. "

đầu ra

Bước 6. nnhỏ nhất(k,đầu vào)

k mục nhỏ nhất được trả lại

import heapq
input = [4,5,7,2,9,1]
heapq.heapify(input)
print("After heapify")
print(input)
print("The K smallest element is")
print(heapq.nsmallest(2,input)) #here K is 2

• Lấy đầu vào là [4,5,7,2,9,1]
• Cấu trúc heap tối thiểu được tạo bằng đầu vào của hàm heapify [1, 2, 4, 5, 9, 7]
• Hai mục nhỏ nhất được trả về bởi hàm nsmallest(2, input) [1,2]

đầu ra

Bước 7. lớn nhất (k, đầu vào)

k mục lớn nhất được trả lại

import heapq
input = [4,5,7,2,9,1]
heapq.heapify(input)
print("After heapify")
print(input)
print("The K largest element is")
print(heapq.nlargest(2,input)) #here K is 2

• Lấy đầu vào là [4,5,7,2,9,1]
• Cấu trúc heap tối thiểu được tạo bằng đầu vào của hàm heapify [1, 2, 4, 5, 9, 7]
• Hai mục nhỏ nhất được trả về bởi hàm nlarget(2, input) [9,7]

đầu ra

Thời gian phức tạp

Mỗi lệnh gọi heapify có chi phí O(log(n)) và chi phí tạo một heap là O. Do đó, đống tòa nhà có độ phức tạp thời gian chạy là O(n log(n)) (n). Kết quả là O(n log(n)) sẽ là tổng thời gian phức tạp

Ứng dụng của đống

• Thuật toán đồ thị như thuật toán của Prim sử dụng cấu trúc dữ liệu heap
• Đối với cơ chế lập lịch công việc trong hệ điều hành, chúng ta có thể sử dụng max-heap và min-heap
• Khi sử dụng phương pháp của Dijkstra, cấu trúc dữ liệu heap được sử dụng
• Heap được sử dụng trong khi triển khai hàng đợi ưu tiên
• Heap được sử dụng trong sắp xếp Heap

Phần kết luận

Khi làm việc với biểu đồ hoặc cây, cấu trúc dữ liệu heap có lợi. Chúng ta có thể tăng hiệu quả của các chương trình khác nhau và báo cáo vấn đề với cấu trúc dữ liệu heap. Vì chúng có hiệu quả trong việc xử lý các tập dữ liệu lớn nên có thể sử dụng min-heap và max-heap. Khi bạn thành thạo với các cấu trúc dữ liệu heap, bạn sẽ rất phù hợp để xử lý các biểu đồ và cây phức tạp

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

Hàng đợi ưu tiên được triển khai heap như thế nào?

Python triển khai hàng đợi ưu tiên như thế nào?

Heapq được triển khai bằng Python như thế nào?