Giới thiệu

Hãy tưởng tượng một sân bay nhộn nhịp với các chuyến bay cất cánh và hạ cánh mỗi phút. Giống như các cơ quan kiểm soát không lưu ưu tiên các chuyến bay dựa trên mức độ khẩn cấp, heap giúp chúng tôi quản lý và xử lý dữ liệu dựa trên các tiêu chí cụ thể, đảm bảo rằng phần dữ liệu “khẩn cấp” hoặc “quan trọng” nhất luôn có thể truy cập được ở trên cùng.

Trong hướng dẫn này, chúng ta sẽ bắt đầu hành trình tìm hiểu về heap từ đầu. Chúng ta sẽ bắt đầu bằng cách làm sáng tỏ đống là gì và các đặc tính vốn có của chúng. Từ đó, chúng ta sẽ đi sâu vào cách triển khai vùng heap của riêng Python, heapq mô-đun và khám phá bộ chức năng phong phú của nó. Vì vậy, nếu bạn đã từng tự hỏi làm thế nào để quản lý hiệu quả một tập hợp dữ liệu động trong đó thường xuyên cần đến phần tử có mức độ ưu tiên cao nhất (hoặc thấp nhất), thì bạn sẽ có cơ hội.

Heap là gì?

Điều đầu tiên bạn muốn hiểu trước khi đi sâu vào cách sử dụng đống là đống là gì. Heap nổi bật trong thế giới cấu trúc dữ liệu với tư cách là một cường quốc dựa trên cây, đặc biệt có kỹ năng về duy trì trật tự và thứ bậc. Mặc dù nó có thể trông giống một cây nhị phân đối với con mắt chưa được huấn luyện, nhưng các sắc thái trong cấu trúc và quy tắc quản lý của nó đã phân biệt nó một cách rõ ràng.

Một trong những đặc điểm xác định của heap là bản chất của nó như một cây nhị phân hoàn chỉnh. Điều này có nghĩa là mọi cấp độ của cây, có lẽ ngoại trừ cấp độ cuối cùng, đã được lấp đầy hoàn toàn. Trong cấp độ cuối cùng này, các nút sẽ xuất hiện từ trái sang phải. Cấu trúc như vậy đảm bảo rằng các đống có thể được biểu diễn và thao tác một cách hiệu quả bằng cách sử dụng mảng hoặc danh sách, với vị trí của mỗi phần tử trong mảng phản ánh vị trí của nó trong cây.

Tuy nhiên, bản chất thực sự của một đống nằm ở chỗ nó đặt hàng. trong một đống tối đa, giá trị của bất kỳ nút nào cũng vượt qua hoặc bằng giá trị của các nút con của nó, định vị phần tử lớn nhất ngay tại gốc. Mặt khác, một đống tối thiểu hoạt động theo nguyên tắc ngược lại: giá trị của bất kỳ nút nào đều nhỏ hơn hoặc bằng giá trị của nút con của nó, đảm bảo phần tử nhỏ nhất nằm ở gốc.

Khuyên bảo: Bạn có thể hình dung một đống như một kim tự tháp số. Đối với vùng heap tối đa, khi bạn đi từ đáy lên đỉnh, các con số sẽ tăng lên, đạt đến giá trị tối đa ở đỉnh cao. Ngược lại, vùng heap tối thiểu bắt đầu với giá trị tối thiểu ở mức cao nhất, với số lượng tăng dần khi bạn di chuyển xuống dưới.

Khi tiến bộ, chúng ta sẽ tìm hiểu sâu hơn về cách các thuộc tính cố hữu này của vùng heap cho phép hoạt động hiệu quả và cách Python hoạt động như thế nào. heapq mô-đun tích hợp liền mạch nhiều khối vào nỗ lực mã hóa của chúng tôi.

Đặc điểm và tính chất của Heap

Heap, với cấu trúc độc đáo và nguyên tắc sắp xếp của chúng, tạo ra một tập hợp các đặc điểm và thuộc tính riêng biệt khiến chúng trở nên vô giá trong các tình huống tính toán khác nhau.

Đầu tiên và quan trọng nhất, đống là vốn đã hiệu quả. Cấu trúc dựa trên cây của chúng, đặc biệt là định dạng cây nhị phân hoàn chỉnh, đảm bảo rằng các hoạt động như chèn và trích xuất các phần tử ưu tiên (tối đa hoặc tối thiểu) có thể được thực hiện theo thời gian logarit, thường là O (log n). Hiệu quả này mang lại lợi ích cho các thuật toán và ứng dụng yêu cầu truy cập thường xuyên vào các phần tử ưu tiên.

Một đặc tính đáng chú ý khác của đống là chúng hiệu quả bộ nhớ. Vì các đống có thể được biểu diễn bằng cách sử dụng mảng hoặc danh sách mà không cần con trỏ rõ ràng tới nút con hoặc nút cha nên chúng tiết kiệm không gian. Vị trí của mỗi phần tử trong mảng tương ứng với vị trí của nó trong cây, cho phép việc di chuyển và thao tác có thể dự đoán được và đơn giản.

Thuộc tính thứ tự của heap, dù là heap tối đa hay heap tối thiểu, đều đảm bảo rằng root luôn giữ phần tử có mức độ ưu tiên cao nhất. Thứ tự nhất quán này cho phép truy cập nhanh vào phần tử có mức độ ưu tiên cao nhất mà không cần phải tìm kiếm trong toàn bộ cấu trúc.

Hơn nữa, đống là linh hoạt. Trong khi các đống nhị phân (trong đó mỗi cha mẹ có nhiều nhất là hai con) là phổ biến nhất, các đống có thể được khái quát hóa để có nhiều hơn hai con, được gọi là đống d-ary. Tính linh hoạt này cho phép tinh chỉnh dựa trên các trường hợp sử dụng cụ thể và yêu cầu về hiệu suất.

Cuối cùng, đống là tự điều chỉnh. Bất cứ khi nào các phần tử được thêm vào hoặc xóa đi, cấu trúc sẽ tự sắp xếp lại để duy trì các thuộc tính của nó. Sự cân bằng động này đảm bảo rằng heap luôn được tối ưu hóa cho các hoạt động cốt lõi của nó.

Khuyên bảo: Các thuộc tính này làm cho cấu trúc dữ liệu heap trở nên phù hợp với thuật toán sắp xếp hiệu quả – sắp xếp heap. Để tìm hiểu thêm về sắp xếp heap trong Python, hãy đọc “Sắp xếp đống trong Python” bài viết.

Khi chúng ta nghiên cứu sâu hơn về cách triển khai và các ứng dụng thực tế của Python, tiềm năng thực sự của heap sẽ bộc lộ trước mắt chúng ta.

Các loại đống

Không phải tất cả các đống đều được tạo ra như nhau. Tùy thuộc vào thứ tự và đặc tính cấu trúc của chúng, đống có thể được phân loại thành các loại khác nhau, mỗi loại có tập hợp ứng dụng và ưu điểm riêng. Hai loại chính là đống tối đa và đống tối thiểu.

Đặc điểm nổi bật nhất của một đống tối đa là giá trị của bất kỳ nút nào đã cho đều lớn hơn hoặc bằng giá trị của các nút con của nó. Điều này đảm bảo rằng phần tử lớn nhất trong heap luôn nằm ở gốc. Cấu trúc như vậy đặc biệt hữu ích khi có nhu cầu truy cập thường xuyên vào phần tử tối đa, như trong các triển khai hàng đợi ưu tiên nhất định.

Bản sao của vùng heap tối đa, a đống tối thiểu đảm bảo rằng giá trị của bất kỳ nút nào đã cho đều nhỏ hơn hoặc bằng giá trị của các nút con của nó. Điều này định vị phần tử nhỏ nhất của heap ở gốc. Vùng heap tối thiểu là vô giá trong các tình huống trong đó phần tử nhỏ nhất có tầm quan trọng hàng đầu, chẳng hạn như trong các thuật toán xử lý dữ liệu theo thời gian thực.

Ngoài các loại chính này, các đống cũng có thể được phân biệt dựa trên hệ số phân nhánh của chúng:

Trong khi đống nhị phân là phổ biến nhất, với mỗi nút cha có nhiều nhất là hai nút con, khái niệm đống có thể được mở rộng đến các nút có nhiều hơn hai nút con. trong một đống d-ary, mỗi nút có nhiều nhất d những đứa trẻ. Biến thể này có thể được tối ưu hóa cho các tình huống cụ thể, như giảm chiều cao của cây để tăng tốc một số thao tác nhất định.

Đống nhị thức là một tập hợp các cây nhị thức được định nghĩa đệ quy. Đống nhị thức được sử dụng trong việc triển khai hàng đợi ưu tiên và cung cấp các hoạt động hợp nhất hiệu quả.

Được đặt tên theo dãy Fibonacci nổi tiếng, đống Fibonacci cung cấp thời gian chạy được khấu hao tốt hơn cho nhiều hoạt động so với đống nhị phân hoặc nhị thức. Chúng đặc biệt hữu ích trong các thuật toán tối ưu hóa mạng.

Triển khai Heap của Python – đống q Mô-đun

Python cung cấp một mô-đun tích hợp sẵn cho các hoạt động của heap – mô-đun heapq mô-đun. Mô-đun này cung cấp một tập hợp các hàm liên quan đến vùng heap cho phép các nhà phát triển chuyển đổi danh sách thành vùng heap và thực hiện các thao tác vùng heap khác nhau mà không cần triển khai tùy chỉnh. Hãy cùng đi sâu vào các sắc thái của mô-đun này và cách nó mang lại cho bạn sức mạnh của đống.

Sản phẩm heapq module không cung cấp kiểu dữ liệu heap riêng biệt. Thay vào đó, nó cung cấp các hàm hoạt động trên danh sách Python thông thường, chuyển đổi và xử lý chúng như đống nhị phân.

Cách tiếp cận này vừa tiết kiệm bộ nhớ vừa tích hợp hoàn hảo với các cấu trúc dữ liệu hiện có của Python.

Đó nghĩa là đống được biểu diễn dưới dạng danh sách in heapq. Cái hay của cách biểu diễn này là tính đơn giản của nó – hệ thống chỉ mục danh sách dựa trên số XNUMX đóng vai trò như một cây nhị phân ẩn. Đối với bất kỳ phần tử nào ở vị trí i, của nó:

• Con bên trái đang ở vị trí 2*i + 1
• Right Child đang ở vị trí 2*i + 2
• Nút cha đang ở vị trí (i-1)//2

Cấu trúc ẩn này đảm bảo rằng không cần biểu diễn cây nhị phân dựa trên nút riêng biệt, giúp các thao tác trở nên đơn giản và mức sử dụng bộ nhớ ở mức tối thiểu.

Không gian phức tạp: Các đống thường được triển khai dưới dạng cây nhị phân nhưng không yêu cầu lưu trữ các con trỏ rõ ràng cho các nút con. Điều này làm cho chúng tiết kiệm không gian với độ phức tạp về không gian là O (n) để lưu trữ n phần tử.

Điều cần thiết cần lưu ý là heapq mô-đun tạo ra các đống tối thiểu theo mặc định. Điều này có nghĩa là phần tử nhỏ nhất luôn ở gốc (hoặc vị trí đầu tiên trong danh sách). Nếu bạn cần một đống tối đa, bạn phải đảo ngược thứ tự bằng cách nhân các phần tử với -1 hoặc sử dụng chức năng so sánh tùy chỉnh.

Python's heapq mô-đun cung cấp một bộ chức năng cho phép các nhà phát triển thực hiện các thao tác heap khác nhau trên danh sách.

Lưu ý: Để sử dụng heapq mô-đun trong ứng dụng của mình, bạn sẽ cần nhập nó bằng cách sử dụng đơn giản import heapq.

Trong các phần sau, chúng ta sẽ đi sâu vào từng thao tác cơ bản này, khám phá cơ chế và trường hợp sử dụng của chúng.

Cách chuyển đổi danh sách thành đống

Sản phẩm heapify() là điểm khởi đầu cho nhiều tác vụ liên quan đến heap. Nó nhận một iterable (thường là một danh sách) và sắp xếp lại các phần tử của nó tại chỗ để đáp ứng các thuộc tính của vùng heap tối thiểu:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

Điều này sẽ xuất ra một danh sách được sắp xếp lại đại diện cho một vùng tối thiểu hợp lệ:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

Độ phức tạp về thời gian: Chuyển đổi danh sách không có thứ tự thành một đống bằng cách sử dụng heapify chức năng là một O (n) hoạt động. Điều này có vẻ phản trực giác, như người ta có thể mong đợi O (nlogn), nhưng do đặc tính của cấu trúc cây nên nó có thể đạt được trong thời gian tuyến tính.

Cách thêm một phần tử vào Heap

Sản phẩm heappush() hàm cho phép bạn chèn một phần tử mới vào heap trong khi vẫn duy trì các thuộc tính của heap:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

Việc chạy mã sẽ cung cấp cho bạn danh sách các phần tử duy trì thuộc tính heap tối thiểu:

[3, 5, 7]

Độ phức tạp về thời gian: Thao tác chèn vào heap, bao gồm việc đặt một phần tử mới vào heap trong khi vẫn duy trì thuộc tính heap, có độ phức tạp về thời gian là O (logn). Điều này là do, trong trường hợp xấu nhất, phần tử có thể phải di chuyển từ lá đến gốc.

Cách xóa và trả về phần tử nhỏ nhất từ ​​Heap

Sản phẩm heappop() hàm trích xuất và trả về phần tử nhỏ nhất từ ​​heap (gốc trong heap tối thiểu). Sau khi loại bỏ, nó đảm bảo danh sách vẫn là một đống hợp lệ:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

Lưu ý: Sản phẩm heappop() là vô giá trong các thuật toán yêu cầu xử lý các phần tử theo thứ tự tăng dần, như thuật toán Heap Sort hoặc khi triển khai hàng đợi ưu tiên trong đó các tác vụ được thực thi dựa trên mức độ khẩn cấp của chúng.

Điều này sẽ xuất ra phần tử nhỏ nhất và danh sách còn lại:

1
[3, 7, 5, 9]

Ở đây, 1 là phần tử nhỏ nhất trong heapvà danh sách còn lại vẫn duy trì thuộc tính heap, ngay cả sau khi chúng tôi xóa 1.

Độ phức tạp về thời gian: Việc loại bỏ phần tử gốc (phần tử nhỏ nhất trong vùng tối thiểu hoặc lớn nhất trong vùng tối đa) và việc sắp xếp lại vùng heap cũng mất nhiều thời gian. O (logn) thời gian.

Cách đẩy một mục mới và bật mục nhỏ nhất

Sản phẩm heappushpop() Hàm là một thao tác kết hợp đẩy một mục mới vào heap, sau đó bật lên và trả về mục nhỏ nhất từ ​​heap:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

Điều này sẽ xuất 3, phần tử nhỏ nhất và in ra phần tử mới heap danh sách bây giờ bao gồm 4 trong khi duy trì thuộc tính heap:

3
[4, 5, 7, 9]

Lưu ý: Sử dụng heappushpop() hiệu quả hơn việc thực hiện các thao tác đẩy một phần tử mới và bật riêng phần tử nhỏ nhất.

Cách thay thế vật phẩm nhỏ nhất và đẩy vật phẩm mới

Sản phẩm heapreplace() hàm lấy phần tử nhỏ nhất và đẩy phần tử mới vào heap, tất cả chỉ trong một thao tác hiệu quả:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

Bản in này 1, phần tử nhỏ nhất và danh sách hiện bao gồm 4 và duy trì thuộc tính heap:

1
[4, 5, 7, 9]

Chú thích: heapreplace() có lợi trong các tình huống phát trực tuyến mà bạn muốn thay thế phần tử nhỏ nhất hiện tại bằng một giá trị mới, chẳng hạn như trong các thao tác cửa sổ cuộn hoặc các tác vụ xử lý dữ liệu theo thời gian thực.

Tìm nhiều điểm cực trị trong Heap của Python

nlargest(n, iterable[, key]) và nsmallest(n, iterable[, key]) các hàm được thiết kế để truy xuất nhiều phần tử lớn nhất hoặc nhỏ nhất từ ​​một iterable. Chúng có thể hiệu quả hơn việc sắp xếp toàn bộ vòng lặp khi bạn chỉ cần một vài giá trị cực trị. Ví dụ: giả sử bạn có danh sách sau và bạn muốn tìm ba giá trị nhỏ nhất và ba giá trị lớn nhất trong danh sách:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Ở đây, nlargest() và nsmallest() các chức năng có thể có ích:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

Điều này sẽ cung cấp cho bạn hai danh sách – một danh sách chứa ba giá trị lớn nhất và danh sách còn lại chứa ba giá trị nhỏ nhất từ data danh sách:

[9, 6, 5]
[1, 1, 2]

Cách xây dựng vùng heap tùy chỉnh của bạn

Trong khi Python heapq module cung cấp một bộ công cụ mạnh mẽ để làm việc với vùng heap, nhưng có những trường hợp trong đó hành vi vùng heap tối thiểu mặc định có thể không đủ. Cho dù bạn đang tìm cách triển khai vùng nhớ heap tối đa hay cần một vùng nhớ heap hoạt động dựa trên các hàm so sánh tùy chỉnh thì việc xây dựng vùng nhớ heap tùy chỉnh có thể là câu trả lời. Hãy cùng khám phá cách điều chỉnh vùng heap theo nhu cầu cụ thể.

Triển khai Max Heap bằng cách sử dụng heapq

Theo mặc định, heapq tạo ra đống tối thiểu. Tuy nhiên, với một thủ thuật đơn giản, bạn có thể sử dụng nó để triển khai vùng heap tối đa. Ý tưởng là đảo ngược thứ tự của các phần tử bằng cách nhân chúng với -1 trước khi thêm chúng vào heap:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

Với cách tiếp cận này, số lớn nhất (về giá trị tuyệt đối) trở thành số nhỏ nhất, cho phép heapq có chức năng duy trì cấu trúc heap tối đa.

Đống với các chức năng so sánh tùy chỉnh

Đôi khi, bạn có thể cần một đống dữ liệu không chỉ so sánh dựa trên thứ tự tự nhiên của các phần tử. Ví dụ: nếu bạn đang làm việc với các đối tượng phức tạp hoặc có tiêu chí sắp xếp cụ thể thì chức năng so sánh tùy chỉnh sẽ trở nên cần thiết.

Để đạt được điều này, bạn có thể gói các phần tử trong một lớp trợ giúp ghi đè các toán tử so sánh:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

Với thiết lập này, bạn có thể xác định bất kỳ hàm so sánh tùy chỉnh nào và sử dụng nó với vùng heap.

Kết luận

Heap cung cấp hiệu suất có thể dự đoán được cho nhiều thao tác, khiến chúng trở thành lựa chọn đáng tin cậy cho các tác vụ dựa trên mức độ ưu tiên. Tuy nhiên, điều cần thiết là phải xem xét các yêu cầu và đặc điểm cụ thể của ứng dụng hiện có. Trong một số trường hợp, việc điều chỉnh cách triển khai của heap hoặc thậm chí chọn cấu trúc dữ liệu thay thế có thể mang lại hiệu suất thực tế tốt hơn.

Heap, như chúng ta đã tìm hiểu, không chỉ là một cấu trúc dữ liệu khác. Chúng đại diện cho sự kết hợp giữa hiệu quả, cấu trúc và khả năng thích ứng. Từ các thuộc tính cơ bản của chúng đến việc triển khai chúng trong Python heapq mô-đun, heap cung cấp một giải pháp mạnh mẽ cho vô số thách thức tính toán, đặc biệt là những vấn đề xoay quanh mức độ ưu tiên.

• Phân phối nội dung và PR được hỗ trợ bởi SEO. Được khuếch đại ngay hôm nay.
• PlatoData.Network Vertical Generative Ai. Trao quyền cho chính mình. Truy cập Tại đây.
• PlatoAiStream. Thông minh Web3. Kiến thức khuếch đại. Truy cập Tại đây.
• Trung tâmESG. Than đá, công nghệ sạch, Năng lượng, Môi trường Hệ mặt trời, Quản lý chất thải. Truy cập Tại đây.
• PlatoSức khỏe. Tình báo thử nghiệm lâm sàng và công nghệ sinh học. Truy cập Tại đây.
• nguồn: https://stackabuse.com/guide-to-heaps-in-python/