Heap là gì

  -  

Thuật toán Heap Sort được dùng để sắp xếp dữ liệu đầu vào theo đồ vật tự tăng dần, kiến tạo thành một heap về 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 bố trí phân nhiều loại dựa trên kết cấu dữ liệu Binary Heap. Heap sort giúp thu xếp các bộ phận trong danh sách sao cho bộ phận lớn nhất được xếp vào cuối danh sách, và quá trình này sẽ tái diễn cho các thành phần 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ờ vào có tốc độ chạy cấp tốc và không thực sự 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à kết cấu dữ liệu quan trọng dựa trên cấu tạo của một cây nhị phân hoàn hảo thỏa mãn trực thuộc tính heap, và rất có thể được màn 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 tàng trữ theo một đồ vật tự quánh 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 để trình diễn cho nằm trong tính heap của một nút vào cây nhị phân, bao gồm 2 loại:

Max heap: phần tử trong nút phụ vương luôn có mức giá trị to hơn so với toàn bộ các thành phần trong nút con. Và quý hiếm nút gốc là lớn nhất so với tất cả các nút khác.Min heap: bộ phận trong nút phụ thân luôn có giá trị nhỏ tuổi hơn so với tất cả các phần tử trong nút con. Và quý hiếm nút nơi bắt đầu là nhỏ dại nhất so với toàn bộ các nút khác.

Ví dụ về kết cấu dữ liệu Min Heap với Max Heap:

*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
Các bộ phận đã được thu xếp đúng

Cách hoạt động của Heap sort trình bày trong đoạn mã bên dưới đây:

for (int i = n – 1; i >= 0; i–)

swap(&arr<0>, &arr);

//Tạo kết cấu heap cho bộ phận gốc để mang 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(“ ”);

 

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 khoản thời gian sắp xếp là: ”);

print(arr, n);

Kết quả dấn được:

 Mảng sau khoản thời gian sắp xếp là: 

3 7 8 11 12 14

Trên đấy là bài reviews cơ phiên bản của hoidapthutuchaiquan.vn về thuật toán Heap sort và ví dụ minh họa. Mong muốn các bạn có thể áp dụng vào trong lịch trình của mình.