Sắp xếp đống C++
+ Tư tưởng của thuật toán Heap-Sort (săp xếp chồng đống) Show 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 + Cài đặt thuật toán [Code Turbo C++] #includehọ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
Ví dụ về cấu trúc dữ liệu Min Heap và Max Heap Cấu hình dữ liệu Max Heap và Min HeapThuậ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ânMộ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 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-heapTrong 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 HeapTiế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 sortThuật toán Heap sort sẽ hoạt động dựa trên các nguyên tắc sau
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. |