Python heapq lấy phần tử nhỏ nhất

Mô-đun Python đống

Heap được sử dụng khi bạn muốn xóa các phần tử có thứ tự/mức độ ưu tiên cao nhất hoặc thấp nhất. Heap cho phép truy cập nhanh vào các phần tử này trong thời gian O(1). Tuy nhiên, heap chỉ cung cấp quyền truy cập nhanh vào các phần tử thấp nhất hoặc lớn nhất;

Bạn có thể đọc thêm về cấu trúc dữ liệu heap tại đây

Trong Python, bạn có mô-đun heapq, trong đó bạn có thể tạo heap tối thiểu hoặc heap tối đa. Theo mặc định, khi bạn tạo heap bằng hàm heapq, heap sẽ luôn là heap tối thiểu, nghĩa là mỗi khi phần tử nhỏ nhất được lấy ra khỏi heap

Mô-đun heapq có một số 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. Các chức năng này được đưa ra dưới đây

• chất thành đống. Hàm này chuyển đổi một cấu trúc dữ liệu có thể lặp lại thành cấu trúc heap, tại chỗ, trong thời gian tuyến tính. Sau khi sử dụng hàm này, các phần tử của heap sẽ được sắp xếp lại để nó có thuộc tính của một min heap
• đống đổ nát. Hàm này chèn một phần tử vào heap và sau khi chèn, thứ tự sẽ được điều chỉnh tương ứng để cấu trúc heap được duy trì. Hàm đẩy trợ giúp thực hiện thao tác này trong thời gian O(log(n)), trong đó n là kích thước của đống
• đống đổ nát. Hàm này xóa và trả về phần tử nhỏ nhất của heap và sau khi xóa, thứ tự được điều chỉnh tương ứng để cấu trúc heap được duy trì. Hàm heappop thực hiện thao tác này trong thời gian O(log(n)), trong đó n là kích thước của heap
• heappushpop. Chức năng này có thể đẩy và bật các phần tử vào heap. Hàm này trước tiên đẩy phần tử được cung cấp* vào heap và sau đó bật phần tử nhỏ nhất ra khỏi heap. Hàm heappushpop thực hiện thao tác này trong thời gian O(log(n)), trong đó n là kích thước của heap
• đống đổ nát. Hàm này cũng đẩy và bật các phần tử trong heap. Nhưng thay vào đó, trước tiên nó bật phần tử nhỏ nhất* từ heap và sau đó *đẩy phần tử được cung cấp trở lại heap. Hàm heapreplace thực hiện thao tác này trong thời gian O(log(n)), trong đó n là kích thước của heap
• lớn nhất. Hàm này trả về k phần tử lớn nhất từ ​​heap. Hàm này chạy trong thời gian O(log(k)), trong đó k là tham số kích thước được truyền cho hàm
• nhỏ nhất. Hàm này trả về k phần tử nhỏ nhất từ ​​heap. Hàm này chạy trong thời gian O(log(k)), trong đó k là tham số kích thước được truyền cho hàm

Tạo một đống trong Python

Trong Python, việc tạo một đống có thể được thực hiện bằng cách sử dụng hàm heapify

Mã số

# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)
print(arr)
đầu ra
Giải trình. Trong đoạn mã trên, bạn có thể thấy rằng chúng ta truyền mảng cho hàm heapify và hàm này đã đưa phần tử nhỏ nhất lên phía trước như đã thấy ở đầu ra

Chèn vào Heap

Trong Python, việc chèn các phần tử vào heap có thể được thực hiện theo nhiều cách. Hãy xem cách chèn các phần tử vào một đống

Mã số

# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)
arr.append(1)
print(arr)
đầu ra
Giải trình. Ở trên các bạn có thể thấy chúng ta đã khởi tạo một mảng có 5 phần tử sau đó chuyển mảng thành heap bằng hàm heapify. Chúng ta sử dụng hàm append để chèn một phần tử vào heap. Phần tử sẽ được thêm vào ở chỉ mục cuối cùng và để biến mảng này thành một đống trở lại, chúng ta phải sắp xếp lại mảng để tất cả các phần tử được sắp xếp hợp lý
Xem đoạn mã dưới đây
# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)
arr.append(1)

# Heapify the array again
heapq.heapify(arr)
print(arr)

# -----------------------------------

đầu ra
Như đã thấy ở đầu ra, sau khi thực hiện thao tác heapify, phần tử nhỏ nhất sẽ xuất hiện phía trước
Tuy nhiên, vì bạn đang sử dụng Python, bạn không cần phải nối thêm các phần tử và lặp đi lặp lại toàn bộ mảng. Chúng tôi sẽ sử dụng chức năng đẩy trợ giúp để chèn các phần tử vào heap. hàm heappush chèn một phần tử vào heap và heapize nó
Mã số
# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)

# Push elements into the heap
heapq.heappush(arr, 1)
print(arr)
đầu ra
Giải trình. Ở trên, bạn có thể thấy rằng chúng tôi đang chèn phần tử 1 vào heap bằng hàm heappush và sau khi chèn, phần tử nhỏ nhất sẽ xuất hiện ở phía trước, điều đó có nghĩa là bạn không phải thực hiện lại thao tác heapify

Xóa phần tử khỏi Heap trong Python

Bạn có thể sử dụng hàm heappop để xóa phần tử khỏi heap. hàm heappop loại bỏ và trả về phần tử nhỏ nhất từ ​​​​heap, có nghĩa là nó luôn loại bỏ phần tử ở chỉ mục đầu tiên

Mã số

# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)

# Pop element from the heap
popEle = heapq.heappop(arr)

# Print the popped element
print(popEle)

# Print the heap after removing an element
print(arr)
đầu ra



Giải trình. Ở trên, bạn có thể thấy chúng tôi sử dụng hàm heappop để xóa phần tử nhỏ nhất khỏi heap. Trong heap của chúng tôi, 2 là phần tử nhỏ nhất, vì vậy chúng tôi đã xóa nó và bây giờ phần tử nhỏ nhất là 6. Phần tử 6 sẽ đến chỉ số 0 như đã thấy trong đầu ra

Thay thế một phần tử trong Heap bằng Python

Hàm heapreplace dùng để thay thế một phần tử trong heap. Hàm này loại bỏ phần tử nhỏ nhất khỏi heap và chèn phần tử mới vào một số vị trí. Nếu phần tử được chèn vào là nhỏ nhất trong heap thì phần tử này sẽ được đưa về chỉ số thứ 0

Mã số

# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)
print(arr)

# Replace the smallest element of the heap with the given element
heapq.heapreplace(arr, 10)
print(arr)
đầu ra
[2, 6, 9, 8, 7]
[6, 7, 9, 8, 10]
Giải trình. Ở trên, bạn có thể thấy rằng lúc đầu phần tử nhỏ nhất trong heap là 2. Chúng tôi thực hiện thao tác thay thế với phần tử 10. Sau khi thực hiện thao tác thay thế, phần tử nhỏ nhất của heap(2) được thay thế bằng phần tử 10. Bây giờ phần tử nhỏ nhất trong heap là 6, vì vậy nó đứng trước heap

Appending và Popping đồng thời

Vì chúng tôi đang sử dụng Python, chúng tôi có thể đồng thời đẩy và bật các phần tử trong heap. Python cung cấp hai chức năng mà bạn có thể thêm và bật các phần tử đồng thời từ heap. Các hàm này là heappushpop và heapreplace. Chúng ta đã thảo luận về chức năng heapreplace. Bây giờ chúng ta sẽ thảo luận về chức năng heappushpop

Điểm chú ý

Hàm heappushpop trước tiên đẩy phần tử đã cung cấp vào heap, sau đó bật phần tử nhỏ nhất khỏi heap và hàm heapreplace trước tiên sẽ đẩy phần tử nhỏ nhất ra khỏi heap rồi đẩy phần tử đã cung cấp trở lại vào heap

ví dụ 1

Mã số

# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)
print(arr)

# Push element 10 into the heap and pop the heap's smallest element
heapq.heappushpop(arr, 10)
print(arr)
đầu ra
[2, 6, 9, 8, 7]
[6, 7, 9, 8, 10]
Giải trình. Đầu tiên phần tử thứ 10 sẽ được đẩy vào heap, sau đó phần tử nhỏ nhất trong heap sẽ được bật ra
ví dụ 2
Mã số
# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)
print(arr)

# Push element 10 into the heap and pop the heap's smallest element
heapq.heappushpop(arr, 1)
print(arr)
đầu ra



# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)
arr.append(1)
print(arr)
0
Giải trình. Bây giờ bạn có thể đang nghĩ, trong kết quả trên, tại sao cả hai đống đều giống nhau? . Bây giờ chúng ta sử dụng hàm heappushpop để chèn và xóa các phần tử khỏi heap. Vì vậy, chức năng này đầu tiên chèn phần tử 1 vào heap. Sau đó, phần tử nhỏ nhất lại đến chỉ số thứ 0 và nó sẽ bị xóa
Xem các bước dưới đây để biết chức năng heappushpop hoạt động như thế nào
Ban đầu, chúng ta có một heap, nghĩa là phần tử nhỏ nhất sẽ ở chỉ số thứ 0
Bây giờ, khi chúng ta sử dụng hàm heappushpop,
Đầu tiên nó chèn phần tử được cung cấp vào heap
Thực hiện thao tác heapify để phần tử nhỏ nhất lại xuất hiện ở phía trước
Nó loại bỏ phần tử nhỏ nhất khỏi heap

Sử dụng Heap để tìm phần tử lớn nhất và nhỏ nhất

Ta không cần sắp xếp mảng để tìm k phần tử nhỏ nhất hoặc lớn nhất. Chúng tôi sẽ sử dụng một số chức năng tích hợp có trong mô-đun heapq. Các chức năng này là lớn nhất và nhỏ nhất. Hàm nlớn nhất trả về n phần tử lớn nhất từ ​​heap và hàm nsmallest trả về n phần tử nhỏ nhất từ ​​heap

Mã số

# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)
arr.append(1)
print(arr)
1
đầu ra
Giải trình. Ở trên, bạn có thể thấy cách chúng tôi tìm thấy hai phần tử lớn nhất và nhỏ nhất từ ​​​​đống mà không sử dụng bất kỳ kỹ thuật sắp xếp hay bất kỳ kỹ thuật nào khác

Tìm hiểu thêm về Heap trong Python

Ở trên, chúng tôi chỉ thảo luận về đống tối thiểu. Khi thực hiện bất kỳ thao tác nào, chẳng hạn như heapify, heappop hoặc heappush, chúng tôi luôn nói rằng phần tử nhỏ nhất có mặt ở chỉ số thứ 0. Còn những phần tử lớn nhất thì sao?

Chúng ta sẽ nói ngắn gọn về max heap. heap tối đa có nghĩa là phần tử lớn nhất sẽ luôn ở chỉ số 0

Giả sử chúng ta có một mảng có năm phần tử

Khi chúng ta thực hiện thao tác heapify trên mảng trên, phần tử nhỏ nhất (2) sẽ xuất hiện ở phía trước. Đây là thuộc tính min-heap.  

Để triển khai heap tối đa, chỉ cần nhân mọi phần tử với -1. Bằng cách này, phần tử lớn nhất sẽ trở thành phần tử nhỏ nhất và nó sẽ xuất hiện ở phía trước

Mã số

# Import heapq module to implement heap
import heapq

# Initialize arr
arr = [9, 7, 2, 8, 6]

# Use heapify to convert arr into a heap
heapq.heapify(arr)
arr.append(1)
print(arr)
2
đầu ra
Giải trình. Bạn có thể thấy rằng 8 là phần tử lớn nhất trong heap. Sau khi ta đổi dấu thì nó trở thành phần tử nhỏ nhất và được đưa lên đầu heap. Bây giờ muốn pop phần tử lớn nhất thì lấy luôn ở chỉ số 0. Chúng ta có thể sử dụng hàm heappop để bật phần tử lớn nhất từ ​​​​đống và nhân phần tử đó với -1 để nó lại chuyển đổi thành số dương