Cấu trúc dữ liệu Heap: Heap là gì?

Cấu trúc dữ liệu Heap là gì?

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

Nói một cách đơn giản, Heap là một cây nhị phân hoàn chỉnh thỏa mãn thuộc tính của heap: mỗi nút cha được sắp xếp nhất quán so với các nút con của nó, điều này làm cho nó lý tưởng cho hàng đợi ưu tiên và thuật toán Heap Sort.

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 Heap:

• Cấu trúc dữ liệu Heap cho phép xóa và chèn trong thời gian logarit – O(log 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 các giá trị như giá trị lớn nhất hoặc nhỏ nhất, lập trình viên có thể tìm ra mối quan hệ giữa nút cha và nút con.
• Bạn có thể áp dụng khái niệm Mô hình Đối tượng Tài liệu Để giúp bạn hiểu cấu trúc dữ liệu Heap một cách trực quan.
• Cấu trúc dữ liệu heap hỗ trợ các thao tác hàng đợi ưu tiên hiệu quả, điều này rất quan trọng đối với các thuật toán đồ thị như thuật toán tìm đường đi ngắn nhất Dijkstra và thuật toán cây bao trùm tối thiểu Prim.

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ý việc chèn và xóa phần tử, 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: Đó là một chiếc abstracCấu trúc dữ liệu chứa các đối tượng được ưu tiên. Mỗi đối tượng hoặc mục đều có một mức độ ưu tiên được gán trước. Do đó, đối tượng hoặc mục được gán mức ưu tiên cao hơn sẽ được phục vụ trước các đối tượng hoặc mục còn lại.
• Vùng nhớ nhị phân (Binary Heap): Cấu trúc dữ liệu heap nhị phân phù hợp với các thao tác heap đơn giản như xóa và chèn. Chúng là cấu trúc mặc định được sử dụng đằng sau hầu hết các hàng đợi ưu tiên trong thư viện chuẩn.
• Đống nhị thức: Một Binomial Heap bao gồm một chuỗi các tập hợp cây nhị thức tạo nên heap. Cây Binomial Heap không phải là cây thông thường theo định nghĩa chặt chẽ của nó. Tổng số phần tử trong một cây nhị thức luôn bằng 2^n.ⁿ đ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 hoạt động sắp xếp của nó. 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 đầu vào thành một Max-Heap. Bạn có thể coi Heap Sort như một cây tìm kiếm nhị phân đượ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. Với đầu vào 12 – 8 – 4 – 2 và 1:

• Min-Heap – Giá trị thấp nhất ở trên cùng
• Max-Heap – Giá trị cao nhất ở trên cùng

Min-Heap

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 của nó. Do đó, gốc của Min-Heap chứa giá trị nhỏ nhất. Min-Heap cũng là một cây nhị phân hoàn chỉnh.

Khi bạn đã có một Min-Heap trong cây, tất cả các lá đều là ứng cử viên khả thi cho giá trị lớn nhất. 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ề Min-Heap

Trong sơ đồ trên, bạn có thể nhận thấy một trình tự rõ ràng 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 tắc ư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 quy tắc Min-Heap được đáp ứng.

Max-Heap

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

Dưới đây là một vài phương pháp thường được sử dụng khi triển khai một Java Max-Heap:

• Thêm vào (): Thêm một phần tử mới vào heap. Nếu sử dụng mảng, các đối tượng được thêm vào cuối mảng, trong khi với cây nhị phân, các đối tượng được thêm từ trên xuống dưới rồi từ trái sang phải.
• Di dời (): Phương pháp này cho phép bạn xóa phần tử đầu tiên khỏi danh sách mảng. Vì phần tử được thêm vào không còn là phần tử lớn nhất nữa, phương pháp Sift-Down luôn đẩy nó đến vị trí mới.
• Lọc xuống (): Phương pháp này so sánh đối tượng gốc với các đối tượng con của nó, sau đó đẩy nút được di dời đến vị trí chính xác của nó.
• Sift-Up (): Nếu bạn sử dụng phương thức mảng để thêm một phần tử mới vào mảng, thì phương thức Sift-Up sẽ giúp di chuyển nút mới được thêm vào đến vị trí chính xác của nó. Phần tử mới trước tiên được so sánh với phần tử cha của nó 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. Tiếp tục thực hiện như vậy cho đến khi phần tử lớn nhất nằm ở đầu mảng.

Đống cơ bản Operations

Để tìm giá trị cao nhất và thấp nhất trong một tập dữ liệu, bạn cần một vài thao tác cơ bản trên heap như tìm, chèn và xóa. Vì các phần tử liên tục xuất hiện và biến mất, bạn cần biết cách:

• 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 cấu trúc dữ liệu heap được gọi là tạo heap. Cho một danh sách các khóa, lập trình viên tạo một heap rỗng và sau đó chèn các khóa khác từng cái một bằng cách sử dụng các thao tác cơ bản trên heap.

Vậy chúng ta hãy bắt đầu xây dựng một Min-Heap bằng phương pháp của William bằng cách chèn các giá trị 12, 2, 8, 1 và 4. Bạn có thể xây dựng heap với n phần tử bằng cách bắt đầu với một heap rỗng và sau đó lần lượt điền vào đó các phần tử khác với độ phức tạp O(n log n).

• Heapify: Một thủ tục chèn giúp chèn các phần tử vào vùng nhớ heap trong khi vẫn giữ nguyên thuộc tính của vùng nhớ heap.

  Ví dụ, thao tác max-heapify kiểm tra xem giá trị của phần tử cha có lớn hơn phần tử con hay 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.ping.

• Hợp nhất: Khi bạn cần kết hợp hai heap thành một, hãy sử dụng thao tác merge để đưa các giá trị từ hai heap lại với nhau. Các heap ban đầu vẫn được giữ nguyê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ó rỗng hay không.

Việc kiểm tra cấu trúc heap trong quá trình sắp xếp hoặc xếp hàng các phần tử là rất quan trọng. Kiểm tra xem có phần tử nào cần xử lý bằng phương thức Is-Empty() hay không là điều cần thiết. Kích thước của heap sẽ giúp xác định vị trí gốc của Max-Heap hoặc Min-Heap, vì vậy bạn cần biết có bao nhiêu phần tử theo sau thuộc tính heap.

• Kích thước máy – Trả về độ lớn hoặc chiều dài của heap. Nó cho biết có bao nhiêu phần tử được lưu trữ theo thứ tự đã sắp xếp.
• Is-Empty – Trả về TRUE nếu heap là null, ngược lại 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 thực tế, ví dụ như:

• Giúp lọc thư rác.
• Triển khai các thuật toán đồ thị như Dijkstra và Prim.
• OperaCân bằng tải hệ thống và nén dữ liệu.
• Tìm kiếm các thống kê về thứ tự, ví dụ như phần tử nhỏ thứ k.
• Triển khai hàng đợi ưu tiên cho phép tìm kiếm các mục trong danh sách với thời gian logarit.
• Cấu trúc dữ liệu Heap cũng được sử dụng để sắp xếp thông qua thuật toán Heap Sort.
• Mô phỏng khách hàng đang xếp hàng chờ.
• Xử lý ngắt trong Operahệ thống ting.
• Trong phương pháp mã hóa Huffman để nén dữ liệu.
• Cung cấp sức mạnh cho thuật toán tìm kiếm "tốt nhất trước" và thuật toán A* trong lập kế hoạch đường đi bằng AI.

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

Các thuộc tính sau mô tả cách hoạt động của hàng đợi ưu tiên được xây dựng trên cấu trúc heap:

• Trong cấu trúc dữ liệu heap ưu tiên, các phần tử trong danh sách được so sánh với nhau để xác định phần tử nào nhỏ hơn hoặc lớn hơn.
• Một phần tử được đưa vào hàng đợi và sau đó được loại bỏ theo thứ tự ưu tiên.
• Mỗi phần tử trong hàng đợi ưu tiên đều có một số duy nhất đượ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ó độ ưu tiên cao nhất sẽ thoát ra trước tiên.

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

Phần tiếp theo sẽ đi sâu vào chi tiết cụ thể. Java Quá trình triển khai biến những quy tắc này thành mã hoạt động.

Sắp xếp đống trong Java với Code Ví dụ

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 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 Code Ví dụ

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)

Đầu ra

[1, 3, 4, 7, 9]

Tiếp theo, bạn sẽ tìm hiểu về Phương pháp chia đôi.

Câu Hỏi Thường Gặp