Heap Sort dựa trên cấu trúc dữ liệu đống nhị phân. Trong đống nhị phân, các nút con của nút cha nhỏ hơn hoặc bằng nó trong trường hợp đống tối đa và các nút con của nút cha lớn hơn hoặc bằng nó trong trường hợp một đống nhỏ nhất.
Ví dụ giải thích tất cả các bước trong Sắp xếp đống như sau.
Mảng ban đầu có 10 phần tử trước khi sắp xếp là -
| 20 | 7 | 1 | 54 | 10 | 15 | 90 | 23 | 77 | 25 |
Mảng này được xây dựng thành một đống tối đa nhị phân bằng cách sử dụng max-heapify. Heap tối đa này được biểu diễn dưới dạng một mảng được đưa ra như sau.
| 90 | 77 | 20 | 54 | 25 | 15 | 1 | 23 | 7 | 10 |
Phần tử gốc của đống tối đa được trích xuất và đặt ở cuối mảng. Sau đó, max heapify được gọi để chuyển phần còn lại của các phần tử thành max heap. Điều này được thực hiện cho đến khi cuối cùng thu được mảng đã sắp xếp, được đưa ra như sau -
| 1 | 7 | 10 | 15 | 20 | 23 | 25 | 54 | 77 | 90 |
Chương trình sắp xếp một mảng gồm 10 phần tử sử dụng thuật toán sắp xếp đống được đưa ra như sau.
Ví dụ
#include<iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int temp;
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
int temp;
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int arr[] = { 20, 7, 1, 54, 10, 15, 90, 23, 77, 25};
int n = 10;
i nt i;
cout<<"Given array is: "<<endl;
for (i = 0; i *lt; n; i++)
cout<<arr[i]<<" ";
cout<<endl;
heapSort(arr, n);
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";
} Đầu ra
Given array is: 20 7 1 54 10 15 90 23 77 25 Sorted array is: 1 7 10 15 20 23 25 54 77 90
Trong chương trình trên, hàm heapify () được sử dụng để chuyển đổi các phần tử thành một heap. Hàm này là một hàm đệ quy và nó tạo ra một đống tối đa bắt đầu từ phần tử mà nó được gọi trong trường hợp này, tức là trong trường hợp này. Đoạn mã chứng minh điều này được đưa ra như sau.
void heapify(int arr[], int n, int i) {
int temp;
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
} Hàm heapSort () sắp xếp các phần tử của mảng bằng cách sử dụng sắp xếp theo đống. Nó bắt đầu từ các nút không phải là lá và gọi heapify () trên mỗi nút. Điều này chuyển đổi mảng thành một đống tối đa nhị phân. Điều này được hiển thị như sau -
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
Sau đó, hàm heapSort () lấy phần tử gốc trong mỗi lần lặp của vòng lặp for và đặt nó ở cuối mảng. Sau đó, heapify () được gọi để đảm bảo rằng phần còn lại của các phần tử là một đống tối đa. Cuối cùng, tất cả các phần tử được lấy ra khỏi đống tối đa bằng phương pháp này và thu được một mảng đã sắp xếp. Điều này được hiển thị như sau.
for (int i = n - 1; i >= 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
} Trong hàm main (), đầu tiên mảng được hiển thị. Sau đó, hàm heapSort () được gọi để sắp xếp mảng. Điều này được cung cấp bởi đoạn mã sau.
cout<<"Given array is: "<<endl; for (i = 0; i < n; i++) cout<<arr[i]<<" "; cout<<endl; heapSort(arr, n);
Cuối cùng, mảng đã sắp xếp được hiển thị. Điều này được hiển thị bên dưới.
printf("\nSorted array is: \n");
for (i = 0; i < n; ++i)
cout<<arr[i]<<" ";