Cấu trúc dữ liệu Heap: Heap là gì? Heap tối thiểu và tối đa (Ví dụ)

Heap là gì?

Heap là một cấu trúc dữ liệu cây chuyên biệt. Heap bao gồm nút trên cùng được gọi là gốc (cha). Con thứ hai của nó là con trái của gốc, trong khi nút thứ ba là con phải của gốc. Các nút liên tiếp được điền từ trái sang phải. Khóa của nút cha so sánh với khóa của nút con và một sự sắp xếp hợp lý xảy ra. Cây dễ hình dung trong đó mỗi thực thể được gọi là một nút. Nút có các khóa duy nhất để nhận dạng.

Tại sao bạn cần Cấu trúc dữ liệu Heap?

Dưới đây là những lý do chính để sử dụng Cấu trúc dữ liệu Heap:

Cấu trúc dữ liệu heap cho phép xóa và chèn theo thời gian logarit – O(log₂NS).
Dữ liệu trong cây được sắp xếp theo một thứ tự cụ thể. Bên cạnh việc cập nhật hoặc truy vấn những thứ như giá trị tối đa hoặc tối thiểu, người lập trình có thể tìm thấy mối quan hệ giữa cha mẹ và con cái.
Bạn có thể áp dụng khái niệm Mô hình Đối tượng Tài liệu để hỗ trợ bạn hiểu cấu trúc dữ liệu heap.

Các loại đống

Cấu trúc dữ liệu heap có nhiều thuật toán khác nhau để xử lý các phần chèn và loại bỏ các phần tử trong cấu trúc dữ liệu heap, bao gồm Hàng đợi ưu tiên, Heap nhị phân, Heap nhị thức và Sắp xếp đống.

Hàng đợi ưu tiên: Nó là một cấu trúc dữ liệu trừu tượng chứa các đối tượng được ưu tiên. Mỗi đối tượng hoặc vật phẩm đều có mức độ ưu tiên được sắp xếp trước cho nó. Vì vậy, đối tượng hoặc hạng mục được gán mức độ ưu tiên cao hơn sẽ nhận được dịch vụ trước những đối tượng hoặc hạng mục còn lại.
Heap nhị phân: Đống nhị phân thích hợp cho các thao tác đơn giản như xóa và chèn.
Heap nhị thức: Một đống nhị thức bao gồm một loạt các tập hợp các cây nhị thức tạo nên heap. Cây Heap nhị thức không phải là cây bình thường vì nó được xác định chặt chẽ. Tổng số phần tử của cây nhị thức luôn có 2ⁿ điểm giao.
Sắp xếp đống: Không giống như hầu hết các thuật toán sắp xếp, heap-sort sử dụng không gian O(1) cho thao tác sắp xếp của nó. Đó là một thuật toán sắp xếp dựa trên so sánh trong đó việc sắp xếp diễn ra theo thứ tự tăng dần bằng cách trước tiên biến nó thành một đống tối đa. Bạn có thể xem Heapsort như một cây tìm kiếm nhị phân chất lượng được nâng cấp.

Thông thường, cấu trúc dữ liệu heap sử dụng hai chiến lược. Đối với đầu vào 12 – 8 – 4 – 2 và 1

Min Heap – giá trị nhỏ nhất ở trên cùng
Max Heap – giá trị cao nhất ở trên cùng

Đống tối thiểu

Trong cấu trúc Min Heap, nút gốc có giá trị bằng hoặc nhỏ hơn các nút con trên nút đó. Nút heap này của Min Heap giữ giá trị tối thiểu. Nhìn chung, cấu trúc heap tối thiểu của nó là một cấu trúc hoàn chỉnh Cây nhị phân.

Khi bạn có một đống Min trong cây, tất cả các lá đều là ứng cử viên khả thi. Tuy nhiên, bạn cần kiểm tra từng lá để có được giá trị Max-heap chính xác.

Ví dụ về Heap tối thiểu

Trong sơ đồ trên, bạn có thể nhận thấy một số trình tự rõ ràng từ nút gốc đến nút thấp nhất.

Giả sử bạn lưu trữ các phần tử trong Mảng Array_N[12,2,8,1,4]. Như bạn có thể thấy từ mảng, phần tử gốc đang vi phạm quyền ưu tiên Min Heap. Để duy trì thuộc tính Min heap, bạn phải thực hiện các thao tác min-heapify để hoán đổi các phần tử cho đến khi các thuộc tính Min heap được đáp ứng.

Đống tối đa

Trong cấu trúc của Max Heap, nút cha hoặc nút gốc có giá trị bằng hoặc lớn hơn nút con của nó trong nút. Nút này giữ giá trị tối đa. Hơn nữa, đây là một cây nhị phân hoàn chỉnh, vì vậy bạn có thể tạo vùng heap tối đa từ một tập hợp các giá trị và chạy nó vào thời gian O(n).

Dưới đây là một số phương pháp để triển khai java max heap

Thêm vào (): đặt một phần tử mới vào một đống. Nếu bạn sử dụng mảng, các đối tượng sẽ được thêm vào cuối mảng, trong khi ở cây nhị phân, các đối tượng sẽ được thêm từ trên xuống dưới rồi từ trái sang phải.
Di dời (): Phương thức này cho phép bạn loại bỏ phần tử đầu tiên khỏi danh sách mảng. Vì phần tử mới được thêm vào không còn lớn nhất nên phương pháp Sift-Down luôn đẩy nó đến vị trí mới.
Sàng lọc xuống ():Phương pháp này so sánh đối tượng gốc với đối tượng con của nó và sau đó đẩy nút mới được thêm vào đúng vị trí của nó.
Sàng lọc (): nếu bạn sử dụng phương thức mảng để thêm một phần tử mới được chèn vào một mảng thì phương thức Sift-Up sẽ giúp nút mới được thêm vào di chuyển đến vị trí mới của nó. Mục mới được chèn trước tiên được so sánh với mục gốc bằng cách mô phỏng cấu trúc dữ liệu cây.
Áp dụng công thức Parent_Index=Child_Index/2. Bạn tiếp tục làm điều này cho đến khi phần tử lớn nhất ở phía trước mảng.

Đống cơ bản Operations

Để tìm giá trị cao nhất và thấp nhất trong một tập hợp dữ liệu, bạn cần nhiều thao tác heap cơ bản như tìm, xóa và chèn. Bởi vì các yếu tố sẽ liên tục đến và đi nên bạn phải:

Tìm kiếm – Tìm kiếm một vật phẩm trong một đống.
Chèn – Thêm một con mới vào heap.
Xóa bỏ – Xóa một nút khỏi đống.

Tạo đống

Quá trình xây dựng heap được gọi là tạo heap. Đưa ra một danh sách các khóa, lập trình viên tạo một vùng heap trống và sau đó chèn lần lượt các khóa khác bằng cách sử dụng các thao tác vùng heap cơ bản.

Vì vậy, hãy bắt đầu xây dựng Min-heap bằng phương pháp của Willaim bằng cách chèn các giá trị 12,2,8,1 và 4 vào một heap. Bạn có thể xây dựng vùng heap có n phần tử bằng cách bắt đầu với vùng heap trống và sau đó lần lượt điền vào vùng heap đó các phần tử khác bằng cách sử dụng thời gian O (nlogn).

Heapify: trong thuật toán chèn, giúp chèn các phần tử vào một heap. Kiểm tra xem cấu trúc dữ liệu heap thuộc tính được tô sáng có được tuân theo hay không.
Ví dụ, một heapify tối đa sẽ kiểm tra xem giá trị của phần tử cha có lớn hơn phần tử con của nó không. Sau đó, các phần tử có thể được sắp xếp bằng các phương pháp như hoán đổi.

Hợp nhất: Xem xét bạn có hai vùng dữ liệu cần kết hợp thành một vùng dữ liệu, hãy sử dụng vùng dữ liệu hợp nhất để mang các giá trị từ hai vùng dữ liệu lại với nhau. Tuy nhiên, các đống ban đầu vẫn được bảo tồn.

Kiểm tra đống

Kiểm tra Heap đề cập đến việc kiểm tra số lượng phần tử trong cấu trúc dữ liệu heap và xác thực xem heap có trống hay không.

Điều quan trọng là phải kiểm tra heaps khi sắp xếp hoặc xếp hàng các phần tử. Kiểm tra xem bạn có phần tử nào để xử lý bằng Is-Empty() hay không là điều quan trọng. Kích thước heap sẽ giúp xác định max-heap hoặc min-heap. Vì vậy, bạn cần biết các phần tử theo sau thuộc tính heap.

Kích thước máy – trả về độ lớn hoặc độ dài của heap. Bạn có thể biết có bao nhiêu phần tử được sắp xếp theo thứ tự.
trống rỗng – nếu heap là NULL, nó trả về TRUE, nếu không, nó trả về FALSE.

Ở đây, bạn đang in tất cả các thành phần trong mức độ ưu tiênQ vòng lặp và sau đó kiểm tra xem mức độ ưu tiênQ có trống không.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Công dụng của cấu trúc dữ liệu Heap

Cấu trúc dữ liệu heap rất hữu ích trong nhiều ứng dụng lập trình ngoài đời thực như:

Giúp lọc thư rác.
Thực hiện các thuật toán đồ thị.
Operating Hệ thống cân bằng tải và nén dữ liệu.
Tìm thứ tự trong số liệu thống kê.
Triển khai hàng đợi Ưu tiên nơi bạn có thể tìm kiếm các mục trong danh sách theo thời gian logarit.
Cấu trúc dữ liệu heap cũng được sử dụng để sắp xếp.
Mô phỏng khách hàng trên một đường dây.
Xử lý ngắt trong Operahệ thống ting.
Trong mã hóa nén dữ liệu của Huffman.

Thuộc tính hàng đợi ưu tiên của heap

Trong vùng ưu tiên, các mục dữ liệu trong danh sách được so sánh với nhau để xác định phần tử nhỏ hơn.
Một phần tử được đặt trong hàng đợi và sau đó bị loại bỏ.
Mỗi phần tử trong Hàng đợi ưu tiên có một số duy nhất liên quan đến nó được xác định là mức độ ưu tiên.
Khi thoát khỏi Hàng đợi ưu tiên, phần tử có mức độ ưu tiên cao nhất sẽ thoát ra trước.

Các bước triển khai Hàng đợi ưu tiên heap trong Java

Sắp xếp heap trong JAVA với ví dụ về mã

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Đầu ra

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Sắp xếp đống trong Python với ví dụ về mã

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)