Heap là gì
Thuật toán Heap Sort được dùng để sắp xếp dữ liệu đầu vào theo thứ tự tăng dần, xây dựng thành một heap tối đa.
Bạn đang xem: Heap là gì
Thuật toán Heap sort là gì?
Thuật toán Heap sort là một kỹ thuật sắp xếp phân loại dựa trên cấu trúc dữ liệu Binary Heap. Heap sort giúp sắp xếp các phần tử trong danh sách sao cho phần tử lớn nhất được xếp vào cuối danh sách, và quá trình này sẽ lặp lại cho các phần tử còn lại trong danh sách.
Heap sort thường được người dùng lựa chọn sử dụng nhiều nhờ có tốc độ chạy nhanh và không quá phức tạp.
Xem thêm: Là Gì? Tạo Ví Và Mua Bán Đồng Tiền Bitcoin Diamond Là Gì Bitcoin Diamond (Bcd) Là Gì
Cấu trúc dữ liệu Heap là gì?
Heap là cấu trúc dữ liệu đặc biệt dựa trên cấu trúc của một cây nhị phân hoàn chỉnh thỏa mãn thuộc tính heap, và có thể được biểu diễn dưới dạng một mảng. Một cây nhị phân sẽ có các mục được lưu trữ theo một thứ tự đặc biệt.
Xem thêm: Nghĩa Của Từ Nomad Là Gì - Nghĩa Của Từ Nomadic Trong Tiếng Việt
Thuật toán Heap sort sẽ được sử dụng để biểu diễn cho thuộc tính heap của một nút trong cây nhị phân, bao gồm 2 loại:
Max heap: Phần tử trong nút cha luôn có giá trị lớn hơn so với tất cả các phần tử trong nút con. Và giá trị nút gốc là lớn nhất so với tất cả các nút khác.Min heap: Phần tử trong nút cha luôn có giá trị nhỏ hơn so với tất cả các phần tử trong nút con. Và giá trị nút gốc là nhỏ nhất so với tất cả các nút khác.Ví dụ về cấu trúc dữ liệu Min Heap và Max Heap:
Cách hoạt động của Heap sort thể hiện trong đoạn mã dưới đây:
for (int i = n – 1; i >= 0; i–) {
swap(&arr<0>, &arr);
//Tạo cấu trúc heap cho phần tử gốc để lấy ra phần tử lớn nhất
heapify(arr, i, 0);
}
#include
void swap(int *a, int *b) {
int c = *a;
*a = *b;
*b = c;
}
void heapify(int arr<>, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left arr
largest = left;
if (right arr
largest = right; if (largest != i) {
swap(&arr, &arr
heapify(arr, n, largest);
}
}
void sort_heap(int arr<>, int n) {
for (int i = n / 2 – 1; i >= 0; i–)
heapify(arr, n, i);
for (int i = n – 1; i >= 0; i–) {
swap(&arr<0>, &arr);
heapify(arr, i, 0);
}
}
void print(int arr<>, int n) {
for (int i = 0; i
printf(“%d “, arr);
printf(“\n”);
}
int main() {
int arr<> = {3, 14, 11, 7, 8, 12};
int n = sizeof(arr) / sizeof(arr<0>);
sort_heap(arr, n);
printf(“Mảng sau khi sắp xếp là: \n”);
print(arr, n); }
Kết quả nhận được:
Mảng sau khi sắp xếp là:
3 7 8 11 12 14
Trên đây là bài giới thiệu cơ bản của hoidapthutuchaiquan.vn về thuật toán Heap sort và ví dụ minh họa. Hy vọng các bạn có thể áp dụng vào trong chương trình của mình.
