Sắp xếp đống C++

+ Tư tưởng của thuật toán Heap-Sort (săp xếp chồng đống)


Ta xem danh sách n phần tử a1, a2, a3,. một  là cây nhị phân.
Cây nhị phân này được xác định như sau. tại nút thứ i tương ứng với chỉ số thứ i của mảng có con trái là nút 2*(i+1)-1 và con phải 2*(i+1) nếu 2*(i+1)-1 và 2* .



Thuật toán được mô tả như sau.
- Build Heap (đống) sao cho mọi nút cha đều có giá trị lớn hơn nút con. Khi đó nút gốc là nút có giá trị lớn nhất.
- Hoán vị trí nút gốc với nút thứ n – 1 và xây dựng lại Heap mới với nút n – 2 và tiếp tục khôi phục vị trí nút gốc với nút lá cuối của cây mới sau n – 2 bước .

Ví dụ. xem xét danh sách trước khi sắp xếp

Sắp xếp đống C++


Sắp xếp đống C++

Sắp xếp đống C++


Sắp xếp đống C++


+ Cài đặt thuật toán [Code Turbo C++]


#include
#include
#define max 100
// nhap day
void NhapMang(int A[],int n) {< . =Largest) {
for(int i=0; icout<<"nhap Phan tu thu A["<cin>>A[i];
}
}
// in day
void XuatMang(int A[],int n) {
cout<for(int i=0; icout<}
// doi cho 2 so
void Swap(int &a,int &b) {
int temp = a;
a = b;
b = temp;
}
//hoan vi nut cha thu i phai lon hon nut con (vun dong)
void Heapify(int A[],int n, int i) {
int Left = 2*(i+1)-1;
int Right = 2*(i+1);
int Largest;
if(LeftA[i])
Largest = Left;
else
Largest = i;
if(RightA[Largest])
Largest = Right;
if(i!=Largest) {
Swap(A[i],A[Largest]);
Heapify(A,n,Large);
}
}
//xay dung Heap sao cho moi nut cha luon lon hon nut con tren cay (tao cay)
void BuildHeap(int A[], int n) {
for(int i = n/2-1; i>=0; i--)
Heapify(A,n,i);
}
// heap-sort
void HeapSort(int A[], int n) {
BuildHeap(A,n);
for(int i = n-1; i>0; i--){
Swap(A[0],A[i]);
Heapify(A,i,0);
}
}
// ham main
void main() {
int A[max], n;
clrscr();
cout<<"Nhap so phan tu:";
cin>>n;
NhapMang(A,n);
cout<
XuatMang(A,n);
cout<
HeapSort(A,n);
XuatMang(A,n);
getch();
}
học thuật toán lập trình, sắp xếp chồng stack, thuật toán c++, thuật toán code c++, thuật toán sắp xếp đống, thuật toán sắp xếp chồng stack, tư duy giải thuật 2 min read

    Chào mừng các bạn đã đến với chủ đề thuật toán lập trình

Hôm nay chúng ta cùng nhau tìm hiểu về thuật toán Heap Sắp xếp (Thuật toán sắp xếp chồng đống)1. Nguyên lý cơ bản của Heap Sort.

– With an section n section file from T1 – T2 – T3…Tn. Ta coi nó như một cây nhị phân

– Quy định cho nhị phân cây như nhau

If an node is at position = i. Thì nút này có 2 nhánh trái và phải tương ứng như sau

+ Nhánh trái là phần tử 2*i + 1 và nhánh phải là 2*i+ 2 với điều kiện là < n

– Nguyên lý được thực hiện như sau

+ Xây dựng sao cho mọi nút cha đều có giá trị lớn hơn nút con => nút gốc đầu tiên sẽ có giá trị lớn nhất

+ Hoán vị trí nút gốc với nút thứ n-1 và xây dựng lại ngăn xếp mới với n-2, sau đó tiếp tục đảo vị trí nút gốc với nút cuối của cây mới sau n-2

Thuật toán Heap Sort được sử 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

Thuật toán Heap sort là gì?

Thuật toán sắp xếp Heap 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 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ờ tốc độ chạy nhanh và không quá phức tạp

Cấu hình dữ liệu cấu trúc 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 phân tích hoàn chỉnh đối tượng heap thuộc tính 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

Thuật toán Heap sort sẽ được sử dụng để biểu diễn thuộc tính heap của một nút trong cây nhị phân, bao gồm 2 loại

  • đống tối đa. 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
  • đống tối thiểu. 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ấu trúc dữ liệu Max Heap và Min HeapCấu hình dữ liệu Max Heap và Min Heap

Thuật toán sắp xếp đống có thể được biểu diễn qua một cây hoặc mảng nhị phân

Làm bất kỳ thế nào để tạo Heap cấu trúc dữ liệu cho một cây nhị phân

Một số thuật toán sắp xếp Heap được sử dụng để thực hiện các thao tác quan trọng trong cấu trúc Heap

Chúng ta có thể sửa đổi một cây nhị phân hoàn chỉnh trở thành Max Heap bằng cách sử dụng hàm Heapify trên tất cả các phần tử không phải là nút lá của Heap. Ta sẽ xem ví dụ về việc tạo Heap cấu trúc dữ liệu cho một cây nhị phân với 3 phần tử

heapify (mảng)

Gốc = mảng[0]

Lớn nhất = lớn nhất ( mảng[0] , mảng [2*0 + 1]. mảng[2*0+2])

nếu (Gốc. = Lớn nhất)

Hoán đổi (Gốc, Lớn nhất)

Trường hợp nút gốc lớn nhấtTrường hợp nút gốc lớn nhấtTrường hợp nút con lớn hơn nút chaTrường hợp nút con lớn hơn nút cha.

Trong trường hợp 1, nút gốc của cây nhị phân là phần tử lớn nhất và chúng ta không cần phải làm gì cả. Trường hợp 2, nút con chứa phần tử lớn hơn nút gốc và ta cần thay đổi để duy trì thuộc tính Max Heap

Ví dụ 2

Hai cây con đều có cấu trúc Max-heapHai cây con đều có cấu trúc Max-heap

Trong ví dụ 2 này, cả 2 cây con đều có cấu trúc Max Heap, tuy nhiên nút gốc trên cùng lại không phải là Max Heap. Nên để duy trì thuộc tính Max Heap cho toàn bộ cây, chúng ta phải đưa 2 cây xuống dưới cho đến khi đúng vị trí của nó

Đẩy 2 cây xuống đúng vị trí để duy trì thuộc tính Max HeapĐẩy 2 cây xuống đúng vị trí để duy trì thuộc tính Max HeapTiếp tục đẩy xuống cho đến khi đúng vị tríTiếp tục đẩy xuống khi đúng vị trí.

Trong một cây nhị phân có cả hai cây con đều là Max Heap, muốn duy trì thuộc tính Max Heap chúng ta cần phải thực hiện quá trình Heapify – tạo cấu trúc dữ liệu Heap từ cây nhị phân Heap nhị phân trên nút gốc nhiều lần cho

Chúng ta có thể kết hợp 2 điều kiện này trong một hàm Heapify như sau

void heapify(int arr[], int n, int i) {

int lớn nhất = i;

int trái = 2 * i + 1;

int ngay = 2 * i + 2;

nếu (trái < n && mảng [trái] > mảng [lớn nhất])

lớn nhất = trái;

nếu (phải < n && mảng[phải] > mảng[lớn nhất])

lớn nhất = đúng;

nếu (lớn nhất. = i) {

hoán đổi (& mảng [i], & mảng [lớn nhất]);

heapify(mảng, n, lớn nhất);

}

}

Chúng ta có thể di chuyển nút gốc đến vị trí chính xác để duy trì thuộc tính Max Heap cho bất kỳ cây nhị phân nào miễn phí là cây con có cấu trúc Max Heap

Hoạt động của thuật toán Heap sort

Thuật toán Heap sort sẽ hoạt động dựa trên các nguyên tắc sau

  • Phần tử lớn nhất được đặt ở nút gốc theo thuộc tính Max Heap
  • Loại bỏ gốc phần tử và đặt nó ở cuối mảng nhị phân. Đặt phần tử cuối cùng của cây nhị phân vào chỗ trống
  • Resize of Heap đi 1 đơn vị
  • Tạo Heap cấu trúc dữ liệu cho phần tử gốc để nút gốc chứa phần tử có giá trị lớn nhất
  • lặp lại quá trình này cho đến khi tất cả các phần tử của danh sách được sắp xếp đúng
Loại bỏ phần tử gốc 14 và đặt ở cuối mảng nhị phân.Loại bỏ gốc phần tử 14 và đặt ở cuối mảng nhị phân. Tạo cấu trúc dữ liệu Heap cho phần tử gốc 12.Tạo cấu trúc dữ liệu Heap cho phần tử gốc 12. Hoán đổi để loại bỏ phần tử gốc 12.Hoán đổi để loại bỏ phần tử gốc 12. Xóa bỏ phần tử gốc 12.Xóa phần tử gốc 12. Tiếp tục tạo cấu trúc dữ liệu Heap.Tiếp tục tạo Heap cấu trúc dữ liệu. Lại hoán đổi để loại bỏ nút gốc 11.Lai rechange to remove root node 11. Xóa bỏ nút gốc 11.Xóa bỏ nút gốc 11. Lại tạo cấu trúc HeapLại tạo Heap cấu trúcHoán đổi để loại bỏ nút gốc 8.Hoán đổi để loại bỏ nút gốc 8. Xóa nút gốc 8.Xóa nút gốc 8. Tạo HeapTạo HeapHoán đổi để loại bỏ nút gốc 7.Hoán đổi để loại bỏ nút gốc 7. Xóa nút gốc 7Xóa nút gốc 7Các phần tử đã được sắp xếp đúngCác phần tử đã được sắp xếp đúng

Cách hoạt động của Heap sort có thể hiển thị trong đoạn mã dưới đây

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

hoán đổi (&arr[0], &arr[i]);

//Tạo cấu trúc heap cho phần tử gốc để lấy phần tử lớn nhất

heapify(mảng, i, 0);

}

#bao gồm

hoán đổi void(int *a, int *b) {

intc = *a;

*a = *b;

*b = c;

}

void heapify(int arr[], int n, int i) {

int lớn nhất = i;

int trái = 2 * i + 1;

int ngay = 2 * i + 2;

nếu (trái < n && mảng [trái] > mảng [lớn nhất])

lớn nhất = trái;

nếu (phải < n && mảng[phải] > mảng[lớn nhất])

lớn nhất = đúng; . = i) {

hoán đổi (& mảng [i], & mảng [lớn nhất]);

heapify(mảng, n, lớn nhất);

}

}

void sort_heap(int arr[], int n) {

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

heapify(mảng, n, i);

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

hoán đổi (&arr[0], &arr[i]);

heapify(mảng, i, 0);

}

}

void print(int arr[], int n) {

cho (int i = 0; i < n; ++i)

printf(“%d “, mảng[i]);

printf(“\n”);

}

int main() {

int arr[] = {3, 14, 11, 7, 8, 12};

int n = sizeof(mảng) / sizeof(mảng[0]);

sort_heap(mảng, n);

printf(“Mảng sau khi sắp xếp là. \N");

in(mảng, n);

Kết quả nhận được

Array after sorting is.  

3 7 8 11 12 14

Trên đây là bài giới thiệu cơ bản của FUNiX 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 chương trình của mình.