Thuật Toán Heap Sort
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 tìm hiểu về thuật toán Heap Sort (Thuật toán sắp xếp vun đống)
1. Nguyên lý cơ bản của Heap Sort.
– Với một tập danh sách n phần từ T1 – T2 – T3… Tn. Ta coi nó như một cây nhị phân.
– Quy định cho cây nhị phân như nhau.
Nếu một node là tại vị trí = i. Thì node 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 đống sao cho với 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ị nút gốc với nút thứ n-1 và xây dựng lại đống mới với n-2, sau đó tiếp tục hoán vị nút gốc với nút cuối của cây mới sau n-2.
2 Thực hành Thuật Toán Heap Sort
#include <iostream> #include <conio.h> void Swap(int& a, int& b) { int temp = a; a = b; b = temp; } void ImplHeapify(int arr[], int n, int i) { int root = i; int l = 2*i + 1; // left position = 2*i + 1 int r = 2*i + 2; // right position = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[root]) root = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[root]) root = r; // If root position is not largest value if (root != i) { Swap(arr[i], arr[root]); ImplHeapify(arr, n, root); } } void ImplHeapSort(int arr[], int n) { for (int i = (n/2) - 1; i >= 0; i--) ImplHeapify(arr, n, i); for (int i = n-1; i >= 0; i--) { Swap(arr[0], arr[i]); ImplHeapify(arr, i, 0); } } void Show(int arr[], int n) { for (int i = 0; i < n; ++i) std::cout << arr[i] << " "; } int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr)/sizeof(arr[0]); ImplHeapSort(arr, n); std::cout << "Sorted List is \n"; Show(arr, n); _getch(); }
TPham