Trong hướng dẫn này, bạn sẽ tìm hiểu cách hoạt động của thuật toán sắp xếp đống. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc về sắp xếp đống trong C, C ++, Java và Python.
Heap Sort là một thuật toán sắp xếp phổ biến và hiệu quả trong lập trình máy tính. Học cách viết thuật toán sắp xếp đống đòi hỏi kiến thức về hai loại cấu trúc dữ liệu - mảng và cây.
Tập hợp số ban đầu mà chúng ta muốn sắp xếp được lưu trữ trong một mảng, ví dụ: (10, 3, 76, 34, 23, 32)và sau khi sắp xếp, chúng ta nhận được một mảng đã sắp xếp(3,10,23,32,34,76)
Sắp xếp đống hoạt động bằng cách hình dung các phần tử của mảng như một loại cây nhị phân hoàn chỉnh đặc biệt được gọi là heap.
Điều kiện tiên quyết là bạn phải biết về cấu trúc dữ liệu heap và cây nhị phân hoàn chỉnh.
Mối quan hệ giữa chỉ mục mảng và phần tử cây
Một cây nhị phân hoàn chỉnh có một đặc tính thú vị mà chúng ta có thể sử dụng để tìm con và cha của bất kỳ nút nào.
Nếu chỉ số của bất kỳ phần tử nào trong mảng là i, phần tử trong chỉ mục 2i+1sẽ trở thành phần tử con bên trái và phần tử trong 2i+2chỉ mục sẽ trở thành phần tử con bên phải. Ngoài ra, phần tử cha của bất kỳ phần tử nào tại chỉ mục i được cho bởi giới hạn dưới của (i-1)/2.
Mối quan hệ giữa chỉ số mảng và heap
Hãy kiểm tra nó ra,
Con bên trái của 1 (chỉ số 0) = phần tử trong (2 * 0 + 1) chỉ mục = phần tử trong 1 chỉ mục = 12 Con bên phải của 1 = phần tử trong (2 * 0 + 2) chỉ số = phần tử trong 2 chỉ mục = 9 Tương tự, Con bên trái của 12 (chỉ số 1) = phần tử trong (2 * 1 + 1) chỉ mục = phần tử trong 3 chỉ mục = 5 Con bên phải của 12 = phần tử trong (2 * 1 + 2) chỉ mục = phần tử trong 4 chỉ mục = 6
Hãy để chúng tôi cũng xác nhận rằng các quy tắc giữ cho việc tìm kiếm cha của bất kỳ nút nào
Cấp độ gốc của 9 (vị trí 2) = (2-1) / 2 = ½ = 0.5 ~ 0 chỉ số = 1 Cấp độ gốc của 12 (vị trí 1) = (1-1) / 2 = 0 chỉ số = 1
Hiểu được ánh xạ của các chỉ mục mảng với các vị trí cây là rất quan trọng để hiểu cách thức hoạt động của Cấu trúc dữ liệu Heap và cách nó được sử dụng để thực hiện Sắp xếp Heap.
Cấu trúc dữ liệu Heap là gì?
Heap là một cấu trúc dữ liệu dựa trên cây đặc biệt. Cây nhị phân được cho là tuân theo cấu trúc dữ liệu đống nếu
- nó là một cây nhị phân hoàn chỉnh
- Tất cả các nút trong cây tuân theo thuộc tính mà chúng lớn hơn phần tử con của chúng, tức là phần tử lớn nhất nằm ở gốc và cả con của nó và nhỏ hơn phần tử gốc, v.v. Một đống như vậy được gọi là một đống tối đa. Nếu thay vào đó, tất cả các nút đều nhỏ hơn nút con của chúng, nó được gọi là min-heap
Sơ đồ ví dụ sau cho thấy Max-Heap và Min-Heap.
Tối đa Heap và Min Heap
Để tìm hiểu thêm về nó, vui lòng truy cập Cấu trúc dữ liệu đống.
Cách "chất đống" cây
Bắt đầu từ một cây nhị phân hoàn chỉnh, chúng ta có thể sửa đổi nó để trở thành Max-Heap bằng cách chạy một hàm gọi là heapify trên tất cả các phần tử không phải lá của heap.
Vì heapify sử dụng đệ quy nên có thể khó nắm bắt. Vì vậy, trước tiên chúng ta hãy nghĩ về cách bạn sẽ đống một cái cây chỉ với ba phần tử.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Làm đống các trường hợp cơ sở
Ví dụ trên cho thấy hai tình huống - một trong đó root là phần tử lớn nhất và chúng ta không cần phải làm gì cả. Và một phần tử khác trong đó phần tử gốc có phần tử lớn hơn khi còn nhỏ và chúng tôi cần hoán đổi để duy trì thuộc tính max-heap.
Nếu bạn đã làm việc với các thuật toán đệ quy trước đây, bạn có thể đã xác định rằng đây phải là trường hợp cơ sở.
Bây giờ chúng ta hãy nghĩ về một kịch bản khác trong đó có nhiều hơn một cấp độ.
Cách đống phần tử gốc khi các cây con của nó đã là đống tối đa
Phần tử trên cùng không phải là max-heap nhưng tất cả các cây con đều là max-heap.
Để duy trì thuộc tính max-heap cho toàn bộ cây, chúng ta sẽ phải tiếp tục đẩy 2 cây xuống dưới cho đến khi nó đến đúng vị trí của nó.
Cách đống phần tử gốc khi các cây con của nó là max-heaps
Do đó, để duy trì thuộc tính max-heap trong một cây mà cả hai cây con đều là max-heap, chúng ta cần chạy heapify trên phần tử gốc nhiều lần cho đến khi nó lớn hơn phần tử con của nó hoặc nó trở thành một nút lá.
Chúng ta có thể kết hợp cả hai điều kiện này trong một hàm heapify như
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
Chức năng này hoạt động cho cả hộp đựng cơ sở và cho một cây có kích thước bất kỳ. Do đó, chúng tôi có thể di chuyển phần tử gốc đến vị trí chính xác để duy trì trạng thái tối đa đống cho bất kỳ kích thước cây nào miễn là các cây con là tối đa đống.
Xây dựng max-heap
Để tạo một đống tối đa từ bất kỳ cây nào, do đó chúng ta có thể bắt đầu xếp đống từng cây con từ dưới lên và kết thúc bằng một đống tối đa sau khi hàm được áp dụng cho tất cả các phần tử bao gồm cả phần tử gốc.
Trong trường hợp một cây hoàn chỉnh, chỉ số đầu tiên của một nút không phải là lá được cho bởi n/2 - 1. Tất cả các nút khác sau đó là các nút lá và do đó không cần phải được xếp thành đống.
Vì vậy, chúng tôi có thể tạo một đống tối đa như
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Tạo mảng và tính toán i 
Các bước để xây dựng tối đa heap cho sắp xếp theo đống 
Các bước để tạo tối đa heap cho sắp xếp theo đống 
Các bước để tạo tối đa heap cho sắp xếp theo đống
Như thể hiện trong sơ đồ trên, chúng tôi bắt đầu bằng cách xếp đống các cây nhỏ nhất thấp nhất và dần dần di chuyển lên cho đến khi chúng tôi đạt đến phần tử gốc.
Nếu bạn đã hiểu tất cả mọi thứ cho đến đây, xin chúc mừng, bạn đang trên con đường để thành thạo việc sắp xếp Heap.
Cách sắp xếp đống hoạt động?
- Vì cây thỏa mãn thuộc tính Max-Heap, nên mục lớn nhất được lưu trữ tại nút gốc.
- Hoán đổi: Loại bỏ phần tử gốc và đặt ở cuối mảng (vị trí thứ n) Đặt mục cuối cùng của cây (đống) vào chỗ trống.
- Xóa: Giảm kích thước của heap đi 1.
- Heapify: Giải phóng phần tử gốc một lần nữa để chúng ta có phần tử cao nhất ở gốc.
- Quá trình được lặp lại cho đến khi tất cả các mục của danh sách được sắp xếp.
Hoán đổi, Xóa và Xử lý đống
Đoạn mã dưới đây cho thấy hoạt động.
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
Ví dụ về Python, Java và C / C ++
Python Java C C ++ # Heap Sort in python def heapify(arr, n, i): # Find largest among root and children largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # If root is not largest, swap with largest and continue heapifying if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build max heap for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Swap arr(i), arr(0) = arr(0), arr(i) # Heapify root element heapify(arr, i, 0) arr = (1, 12, 9, 5, 6, 10) heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr(i), end='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l arr(largest)) largest = l; if (r arr(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Sắp xếp đống phức tạp
Heap Sort có O(nlog n)sự phức tạp về thời gian cho tất cả các trường hợp (trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất).
Hãy để chúng tôi hiểu lý do tại sao. Chiều cao của một cây nhị phân hoàn chỉnh chứa n phần tử làlog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Mặc dù Heap Sort có O(n log n)độ phức tạp về thời gian ngay cả trong trường hợp xấu nhất, nó không có nhiều ứng dụng hơn (so với các thuật toán sắp xếp khác như Quick Sort, Merge Sort). Tuy nhiên, cấu trúc dữ liệu cơ bản của nó, heap, có thể được sử dụng hiệu quả nếu chúng ta muốn trích xuất phần nhỏ nhất (hoặc lớn nhất) từ danh sách các mục mà không cần phải giữ các mục còn lại theo thứ tự đã sắp xếp. Ví dụ: Hàng đợi ưu tiên.
