Hàng đợi ưu tiên là hàng đợi trong đó các phần tử có một tham số khác được gọi là mức độ ưu tiên. Dựa trên mức độ ưu tiên của phần tử, các phần tử đó được đẩy/bật khỏi Hàng đợi trước
Mô-đun này sử dụng một đống nhỏ nhị phân để xây dựng hàng đợi ưu tiên
Thuộc tính chính của cấu trúc dữ liệu hàng đợi heap này là phần tử nhỏ nhất luôn được bật ra trước
Ngoài ra, một khi bất kỳ phần tử nào được đẩy/bật, loại cấu trúc tương tự sẽ được duy trì
Cấu trúc dữ liệu này có một số lượng lớn các ứng dụng, bao gồm sắp xếp
Hãy hiểu làm thế nào bây giờ chúng ta có thể sử dụng mô-đun này
Hiểu mô-đun heapq Python
Mô-đun này là một phần của thư viện tiêu chuẩn, vì vậy không cần cài đặt riêng mô-đun này bằng cách sử dụng pip
Để nhập mô-đun heapq, chúng ta có thể làm như sau
import heapq
Trong mô-đun heapq
, chúng tôi chủ yếu yêu cầu 3 phương thức mà chúng tôi cần để xây dựng và thao tác với hàng đợi ưu tiên của mình
heappush[heap, item]
-> Đẩyitem
lênimport heapq a = [1, 4, 3, 5, 2] print["List =", a] # Convert the iterable [list] into a min-heap in-place heapq.heapify[a] print["Min Heap =", a]
0 và duy trì thuộc tính min-heapimport heapq a = [1, 4, 3, 5, 2] print["List =", a] # Convert the iterable [list] into a min-heap in-place heapq.heapify[a] print["Min Heap =", a]
1 -> Bật và trả về mục nhỏ nhất từ đống. Nếu heap trống, chúng ta sẽ nhận được một Ngoại lệimport heapq a = [1, 4, 3, 5, 2] print["List =", a] # Convert the iterable [list] into a min-heap in-place heapq.heapify[a] print["Min Heap =", a]
2import heapq a = [1, 4, 3, 5, 2] print["List =", a] # Convert the iterable [list] into a min-heap in-place heapq.heapify[a] print["Min Heap =", a]
3 -> Chuyển đổi iterable [danh sách, v.v.] thành min-heap. Điều này sửa đổi iterable tại chỗ
Hãy lấy một ví dụ đơn giản về việc xây dựng hàng đợi ưu tiên từ một danh sách các số nguyên bình thường
import heapq a = [1, 4, 3, 5, 2] print["List =", a] # Convert the iterable [list] into a min-heap in-place heapq.heapify[a] print["Min Heap =", a]
đầu ra
List = [1, 4, 3, 5, 2] Min Heap = [1, 2, 3, 5, 4]
Như bạn có thể thấy, phương thức
import heapq a = [1, 4, 3, 5, 2] print["List =", a] # Convert the iterable [list] into a min-heap in-place heapq.heapify[a] print["Min Heap =", a]4 sửa đổi danh sách tại chỗ và chuyển đổi nó thành min-heap
Để quan sát lý do tại sao nó là một đống nhỏ, chỉ cần vẽ biểu diễn cây của cả hai danh sách
Đối với một biểu diễn min-heap từ một danh sách, đối với một nút có chỉ số _______1_______5, các phần tử con của nó có các chỉ số _______1_______6 và _______1_______7
Đối với một đống nhỏ, cha mẹ phải nhỏ hơn cả hai con của nó
Như bạn có thể thấy, danh sách thứ hai thực sự tuân theo thuộc tính min-heap của chúng ta. Vì vậy, chúng tôi đã xác minh rằng phương pháp
import heapq a = [1, 4, 3, 5, 2] print["List =", a] # Convert the iterable [list] into a min-heap in-place heapq.heapify[a] print["Min Heap =", a]4 cung cấp cho chúng tôi heap tối thiểu chính xác
Bây giờ chúng tôi sẽ đẩy và bật đến/từ đống của chúng tôi
import heapq a = [1, 4, 3, 5, 2] print["List =", a] # Convert the iterable [list] into a min-heap in-place heapq.heapify[a] print["Min Heap =", a] # Use heappush heapq.heappush[a, 10] print["After heappush[], Min Heap =", a] # Use array indexing to get the smallest element print[f"Smallest element in the heap queue = {a[0]}"] # Use heappop[] and return the popped element popped_element = heapq.heappop[a] print[f"Popped element = {popped_element}, Min Heap = {a}"]
đầu ra
List = [1, 4, 3, 5, 2] Min Heap = [1, 2, 3, 5, 4] After heappush[], Min Heap = [1, 2, 3, 5, 4, 10] Smallest element in the heap queue = 1 Popped element = 1, Min Heap = [2, 4, 3, 5, 10]
Như bạn có thể thấy, chúng ta có thể dễ dàng thực hiện các thao tác mong muốn trên hàng đợi heap này. Bây giờ chúng ta hãy xem việc sử dụng min-heap này để sắp xếp danh sách của chúng ta bằng cách sử dụng heapsort
import heapq def heapsort[iterable]: h = [] for value in iterable: # Push the elements onto the heap heapq.heappush[h, value] # Keep popping the smallest elements and appending them to our sorted list return [heapq.heappop[h] for i in range[len[h]]] sorted_list = heapsort[[1, 3, 5, 7, 9, 2, 4, 6, 8, 0]] print[sorted_list]
đầu ra
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Tuyệt. Thật vậy, chúng tôi đã sử dụng thuộc tính hàng đợi heap để sắp xếp danh sách của chúng tôi
Phần kết luận
Trong bài viết này, chúng ta đã tìm hiểu về cách sử dụng mô-đun heapq trong Python và xem cách chúng ta có thể sử dụng thuộc tính min-heap để sắp xếp danh sách không có thứ tự