Cây Heap (Heap Trees): Chuyên Sâu về Max Heap, Min Heap và Ứng Dụng

Chào mừng bạn đến với bài viết thứ 13 trong series về cấu trúc dữ liệu và giải thuật.

Hôm nay, chúng ta sẽ khám phá một cấu trúc dữ liệu mạnh mẽ: Cây Heap (Heap Trees).

Chúng ta sẽ đi sâu vào Max Heap và Min Heap. Bài viết cũng trình bày cách ứng dụng Heap.

Ứng dụng này bao gồm Sắp xếp vun đống (Heap Sort) và Hàng đợi ưu tiên (Priority Queue).

Các ví dụ minh họa bằng ngôn ngữ lập trình Java sẽ giúp bạn dễ dàng nắm bắt kiến thức.

1. Giới Thiệu về Cây Heap

Cây Heap là một cấu trúc dữ liệu cây đặc biệt dựa trên cây nhị phân.

Nó thỏa mãn tính chất Heap: giá trị của mỗi nút phải lớn hơn hoặc bằng (Max Heap) hoặc nhỏ hơn hoặc bằng (Min Heap) giá trị của các nút con của nó.

Heap thường được biểu diễn bằng mảng, giúp truy cập các phần tử một cách hiệu quả.

Vị trí của nút cha, con trái và con phải có thể được tính toán dễ dàng bằng các phép toán đơn giản.

2. Max Heap và Min Heap

Có hai loại Heap chính: Max Heap và Min Heap.

2.1. Max Heap

Trong Max Heap, giá trị của nút gốc là lớn nhất trong toàn bộ Heap.

Giá trị của mỗi nút cha phải 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 luôn nằm ở gốc cây.

Max Heap thường được sử dụng để tìm phần tử lớn nhất một cách nhanh chóng.

2.2. Min Heap

Ngược lại với Max Heap, trong Min Heap, giá trị của nút gốc là nhỏ nhất.

Giá trị của mỗi nút cha phải nhỏ hơn hoặc bằng giá trị của các nút con của nó.

Phần tử nhỏ nhất luôn nằm ở gốc cây trong Min Heap.

Min Heap được sử dụng để tìm phần tử nhỏ nhất một cách hiệu quả.

3. Các Thao Tác Cơ Bản trên Heap

Một số thao tác cơ bản trên Heap bao gồm:

• Thêm phần tử (Insert): Thêm một phần tử mới vào Heap. Sau đó, ta cần "vun đống" (heapify) để đảm bảo tính chất Heap được duy trì.
• Xóa phần tử (Delete): Xóa một phần tử khỏi Heap. Thông thường, ta xóa phần tử ở gốc (phần tử lớn nhất/nhỏ nhất). Sau đó, ta cần vun đống lại.
• Tìm phần tử lớn nhất/nhỏ nhất (Find Max/Min): Trả về phần tử lớn nhất (trong Max Heap) hoặc nhỏ nhất (trong Min Heap) mà không xóa nó khỏi Heap.
• Vun đống (Heapify): Đảm bảo rằng một cây con thỏa mãn tính chất Heap.

4. Sắp Xếp Vun Đống (Heap Sort)

Heap Sort là một thuật toán sắp xếp hiệu quả sử dụng cấu trúc dữ liệu Heap.

Đầu tiên, ta xây dựng một Max Heap từ mảng đầu vào.

Sau đó, ta lặp lại các bước sau:

1. Hoán đổi phần tử gốc (lớn nhất) với phần tử cuối cùng của mảng.
2. Giảm kích thước Heap đi 1.
3. Vun đống lại Heap với gốc là phần tử mới.

Sau khi lặp lại các bước trên, mảng sẽ được sắp xếp theo thứ tự tăng dần.

Heap Sort có độ phức tạp thời gian là O(n log n), đây là một thuật toán sắp xếp khá nhanh.

Ví dụ Heap Sort bằng Java:

public class HeapSort {

 public void sort(int arr[]) {
 int n = arr.length;

 // Build heap (rearrange array)
 for (int i = n / 2 - 1; i >= 0; i--)
 heapify(arr, n, i);

 // One by one extract an element from heap
 for (int i=n-1; i>=0; i--) {
 // Move current root to end
 int temp = arr[0];
 arr[0] = arr[i];
 arr[i] = temp;

 // call max heapify on the reduced heap
 heapify(arr, i, 0);
 }
 }

 // To heapify a subtree rooted with node i which is
 // an index in arr[]. n is size of heap
 void heapify(int arr[], int n, int i) {
 int largest = i; // Initialize largest as root
 int l = 2*i + 1; // left = 2*i + 1
 int r = 2*i + 2; // right = 2*i + 2

 // If left child is larger than root
 if (l < n && arr[l] > arr[largest])
 largest = l;

 // If right child is larger than largest so far
 if (r < n && arr[r] > arr[largest])
 largest = r;

 // If largest is not root
 if (largest != i) {
 int swap = arr[i];
 arr[i] = arr[largest];
 arr[largest] = swap;

 // Recursively heapify the affected sub-tree
 heapify(arr, n, largest);
 }
 }

 // Driver program
 public static void main(String args[]) {
 int arr[] = {12, 11, 13, 5, 6, 7};
 int n = arr.length;

 HeapSort ob = new HeapSort();
 ob.sort(arr);

 System.out.println("Sorted array is");
 for (int i=0; i

import java.util.PriorityQueue;

public class PriorityQueueExample {
 public static void main(String[] args) {
 // Creating a Priority Queue (Min Heap by default)
 PriorityQueue pq = new PriorityQueue<>();

 // Adding elements to the Priority Queue
 pq.add(10);
 pq.add(20);
 pq.add(15);

 // Printing the top element (smallest element)
 System.out.println("Top element: " + pq.peek()); // Output: 10

 // Removing the top element
 System.out.println("Removed element: " + pq.poll()); // Output: 10

 // Printing the updated top element
 System.out.println("New top element: " + pq.peek()); // Output: 15
 }
}