Thuật toán sắp xếp Heap Sort là một trong những thuật toán sắp xếp dựa trên việc tạo ra một cây nhị phân đầy đủ với các phần tử của mảng và sắp xếp các phần tử theo thứ tự tăng dần hoặc giảm dần.
Các bước thực hiện thuật toán Heap Sort:
- Xây dựng một cây nhị phân đầy đủ từ mảng đầu vào.
- Sắp xếp cây nhị phân bằng cách sắp xếp các nút của cây.
- Lấy ra các phần tử từ cây nhị phân đã sắp xếp để tạo ra mảng kết quả.
Để cài đặt thuật toán Heap Sort trong Java, chúng ta có thể sử dụng một mảng số nguyên và sau đó sắp xếp các phần tử trong mảng theo thứ tự tăng dần bằng cách sử dụng Heap Sort.
public static void heapSort(int[] arr) {
int n = arr.length;
// Xây dựng heap từ mảng ban đầu
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Thực hiện sắp xếp Heap
for (int i = n - 1; i >= 0; i--) {
// Đưa phần tử lớn nhất (gốc) vào cuối mảng
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Xây dựng lại heap với phần tử còn lại
heapify(arr, i, 0);
}
}
public static void heapify(int[] arr, int n, int i) {
int largest = i; // Khởi tạo largest là gốc
int left = 2 * i + 1; // Vị trí con trái
int right = 2 * i + 2; // Vị trí con phải
// Nếu con trái lớn hơn gốc
if (left < n && arr[left] > arr[largest])
largest = left;
// Nếu con phải lớn hơn gốc
if (right < n && arr[right] > arr[largest])
largest = right;
// Nếu largest không phải là gốc
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Xây dựng lại heap ở subtree bị ảnh hưởng
heapify(arr, n, largest);
}
}
Trong đó, heapify được sử dụng để xây dựng hoặc tái cấu trúc một heap. heapSort được sử dụng để sắp xếp một mảng bằng cách sử dụng Heap Sort.
Để sử dụng thuật toán này, chúng ta có thể khởi tạo một mảng số nguyên và gọi phương thức heapSort:
int[] arr = {5, 2, 8, 3, 1};
heapSort(arr);
System.out.println(Arrays.toString(arr));
Kết quả đầu ra sẽ là: [1, 2, 3, 5, 8]