Trong bài viết này, chúng tôi sẽ tìm hiểu thêm về Max Heap (được gọi là hàng đợi Heap trong Python). Chúng tôi đã tìm hiểu về HEAP và các chức năng thư viện của nó (trong mô -đun FEAPQ) trong Python. Bây giờ chúng ta sẽ tìm hiểu về Max Heap và việc triển khai của nó và sau đó xem mã Python để thực hiện các lỗi Max Heap là một cây nhị phân hoàn chỉnh (cây nhị phân hoàn chỉnh là một cây được lấp đầy hoàn toàn, ngoại trừ các nút ngoài cùng bên phải ở cấp độ sâu nhất/cuối cùng) trong đó mỗi nút lớn hơn hoặc bằng với tất cả trẻ em. Do đó, nút gốc của một đống là yếu tố lớn nhất. Cấu trúc dữ liệu HEAP thường được sử dụng để thể hiện hàng đợi ưu tiên và HEAP tối đa có thể được hiểu là hàng đợi ưu tiên với phần tử tối đa là ưu tiên cao nhất. Max-heap được thể hiện như thế nào trong một mảng?Chúng ta đã thấy làm thế nào một đống được biểu diễn trong bộ nhớ dưới dạng một mảng, chỉ là một lời nhắc nhanh rằng:
 Một đống trong Python là theo mặc định Min-heap và được sử dụng bằng mô-đun FEAPQ, ____ ____, Để tạo và sử dụng tối đa bằng cách sử dụng các chức năng thư viện, chúng ta có thể nhân mỗi phần tử với -1 và sau đó sử dụng hàm thư viện Heap và do đó nó sẽ hoạt động như một phần lớn. Bây giờ chúng ta hãy hiểu cách các chức năng tối đa hoạt động và cách chúng ta có thể viết mã để thực hiện các chức năng này từ đầu. Hiểu các chức năng để thực hiện Max Heap1. Chức năng tối đamax-heapify functionChức năng này tạo ra một nút và tất cả hậu duệ của nó (nút con và con của họ) theo thuộc tính HEAP tối đa. Nó sắp xếp lại các nút bằng cách hoán đổi chúng để làm cho đống đã cho thành nút lớn nhất trong cây con của nó, theo thuộc tính tối đa. Đầu tiên nó tìm thấy nút có giá trị lớn nhất trong số các nút đã cho và tất cả trẻ em của nó. Sau đó, nó hoán đổi nút đã cho, (giả sử i) với nút giá trị tối đa được tìm thấy (giả sử J), sau đó gọi hàm Vì nhiều nhất, nó phải đi qua độ sâu của cây, độ phức tạp của thời gian của nó là O (d), D là độ sâu, hoặc, theo số lượng nút, O (log n), n là số lượng của các yếu tố trong đống. 2. Chức năng xây dựngbuild-heap functionChức năng này xây dựng một đống từ một danh sách tùy ý (hoặc bất kỳ sự khác biệt nào khác), nghĩa là, nó lấy danh sách và sắp xếp lại từng phần tử để đáp ứng thuộc tính tối đa. Nó chỉ đơn giản là được thực hiện bằng cách áp dụng 3. HEAPPOPFUNCTIONheappop functionHàm này bật ra giá trị tối đa (phần tử gốc) của đống. Điều này thực sự được thực hiện bằng cách hoán đổi nút gốc với nút cuối cùng và xóa nút cuối cùng bây giờ (chứa giá trị tối đa ngay bây giờ) và sau đó gọi Vì chúng ta chỉ cần đối phó với con cháu, nên độ phức tạp của thời gian là o (log n), trong đó n là số lượng phần tử hoặc o (h), trong đó h là chiều cao của cây là log n vì nó là hoàn chỉnh cây. 4. Chức năng nặng nềheappush functionHàm này đẩy một phần tử mới vào đống và sắp xếp nó vào vị trí chính xác của nó, duy trì thuộc tính heap. Điều này thực sự được thực hiện bằng cách thêm một nút mới vào cuối đống. Bây giờ để duy trì thuộc tính heap, chúng tôi đi qua nút cuối cùng (và hoán đổi khi cần thiết) để khắc phục thuộc tính heap có thể bị vi phạm do thêm phần tử được đẩy. Theo cách tương tự như 5. Chiết xuất hàmextractMax functionHàm này trả về mức độ ưu tiên nhất (phần tử gốc hoặc phần tử lớn nhất) từ đống. Vì chúng ta chỉ cần trả về giá trị của gốc và không thay đổi cho đống và gốc có thể truy cập được trong thời gian O (1), do đó độ phức tạp của thời gian của hàm là O (1). Bây giờ, chúng tôi sẽ thực hiện một heap tối đa trong Python. Chúng tôi sử dụng danh sách [15, 7, 9, 4, 13] trong mã và chuyển đổi nó thành một đống tối đa bằng hàm Parent Node is 15 Left Child is 13 Right Child is 9 Parent Node is 13 Left Child is 4 Right Child is 72. Các đống được làm sẽ trông như thế này: Implementation: import sys
#defining a class max_heap for the heap data structure
class max_heap:
def __init__(self, sizelimit):
self.sizelimit = sizelimit
self.cur_size = 0
self.Heap = [0]*(self.sizelimit + 1)
self.Heap[0] = sys.maxsize
self.root = 1
# helper function to swap the two given nodes of the heap
# this function will be needed for max-heapify and insertion
# in order to swap nodes which are not in order (not satisfy max-heap property)
def swapnodes(self, node1, node2):
self.Heap[node1], self.Heap[node2] = self.Heap[node2], self.Heap[node1]
# THE MAX_HEAPIFY FUNCTION
def max_heapify(self, i):
# If the node is a not a leaf node and is lesser than any of its child
if not (i >= (self.cur_size//2) and i <= self.cur_size):
if (self.Heap[i] < self.Heap[2 * i] or self.Heap[i] < self.Heap[(2 * i) + 1]):
if self.Heap[2 * i] > self.Heap[(2 * i) + 1]:
# Swap the node with the left child and call the max_heapify function on it
self.swapnodes(i, 2 * i)
self.max_heapify(2 * i)
else:
# Swap the node with right child and then call the max_heapify function on it
self.swapnodes(i, (2 * i) + 1)
self.max_heapify((2 * i) + 1)
# THE HEAPPUSH FUNCTION
def heappush(self, element):
if self.cur_size >= self.sizelimit :
return
self.cur_size+= 1
self.Heap[self.cur_size] = element
current = self.cur_size
while self.Heap[current] > self.Heap[current//2]:
self.swapnodes(current, current//2)
current = current//2
# THE HEAPPOP FUNCTION
def heappop(self):
last = self.Heap[self.root]
self.Heap[self.root] = self.Heap[self.cur_size]
self.cur_size -= 1
self.max_heapify(self.root)
return last
# THE BUILD_HEAP FUNCTION
def build_heap(self):
for i in range(self.cur_size//2, 0, -1):
self.max_heapify(i)
# helper function to print the heap
def print_heap(self):
for i in range(1, (self.cur_size//2)+1):
print("Parent Node is "+ str(self.Heap[i])+" Left Child is "+ str(self.Heap[2 * i]) + " Right Child is "+ str(self.Heap[2 * i + 1]))
maxHeap = max_heap(10)
maxHeap.heappush(15)
maxHeap.heappush(7)
maxHeap.heappush(9)
maxHeap.heappush(4)
maxHeap.heappush(13)
maxHeap.print_heap()
Output: Parent Node is 15 Left Child is 13 Right Child is 9 Parent Node is 13 Left Child is 4 Right Child is 7 Đầu ra có thể được xác minh từ hình minh họa được đưa ra trong hình ảnh ví dụ. Sự kết luậnTrong bài viết này, chúng tôi đã tìm hiểu về tối đa. Chúng tôi đã nghiên cứu cách các chức năng cho hoạt động của Parent Node is 15 Left Child is 13 Right Child is 9 Parent Node is 13 Left Child is 4 Right Child is 76. Chúng tôi tiếp tục thực hiện các chức năng này trong Python từ đầu. Hãy theo dõi các bài viết nhiều thông tin hơn. Học hỏi! Làm thế nào để bạn viết Max Heap?Thuật toán xóa HEAP tối đa Bước 1 - Xóa nút gốc. Bước 2 - Di chuyển phần tử cuối cùng của cấp độ cuối cùng sang root. Bước 3 - So sánh giá trị của nút con này với cha mẹ của nó. Bước 4 - Nếu giá trị của cha mẹ nhỏ hơn con, sau đó trao đổi chúng.Step 1 − Remove root node. Step 2 − Move the last element of last level to root. Step 3 − Compare the value of this child node with its parent. Step 4 − If value of parent is less than child, then swap them.
Làm thế nào để bạn tạo ra một đống trong Python?Một đống được tạo ra bằng cách sử dụng thư viện sẵn có của Python có tên là Feapq ... Heapify - Hàm này chuyển đổi một danh sách thông thường thành một đống..... Heappush - Hàm này thêm một phần tử vào đống mà không làm thay đổi đống hiện tại .. Heppop - Hàm này trả về phần tử dữ liệu nhỏ nhất từ đống .. Có một heap tối đa được xây dựng trong Python?Một đống trong Python là theo mặc định Min-heap và được sử dụng bằng các hàm Heapf, Heppop và Heppush của mô-đun Heapq.Để tạo và sử dụng tối đa bằng cách sử dụng các chức năng thư viện, chúng ta có thể nhân mỗi phần tử với -1 và sau đó sử dụng hàm thư viện Heap và do đó nó sẽ hoạt động như một phần lớn.To create and use a max-heap using library functions, we can multiply each element with -1 and then use the heap library function, and hence it will act as a max-heap.
Python là đống tối thiểu hay tối đa?8 Cấu trúc dữ liệu phổ biến Mỗi lập trình viên phải biết mô -đun HEAPQ của Python thực hiện thuật toán Hàng đợi HEAP.Nó sử dụng các đống tối thiểu trong đó chìa khóa của cha mẹ nhỏ hơn hoặc bằng với con của nó.min heap where the key of the parent is less than or equal to those of its children. |
