Làm cách nào để cài đặt heapq trong Python?

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) -> Đẩy item lên

  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)
  

  0 và duy trì thuộc tính min-heap

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

  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)
  

  2

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

  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)

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

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ự

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

Nhập heapq trong Python là gì?

Heapq có phải là một phần của Python không?

Có cần nhập Heapq không?