Heap Sort trong C#

Heap Sort là thuật toán sắp xếp sử dụng cấu trúc dữ liệu heap. Mỗi lần phần tử gốc của heap (phần tử lớn nhất) bị loại bỏ và lưu vào mảng. Nó được thay thế bằng phần tử lá bên phải nhất và heap được thiết lập lại. Quá trình lặp lại cho đến khi không còn phần tử nào trong heap và mảng được sắp xếp.

Ví dụ

using System;

namespace HeapSortDemo
{
    public class Example
    {
        static void HeapSort(int[] arr, int n)
        {
            // Xây dựng max heap
            for (int i = n / 2 - 1; i >= 0; i--)
                Heapify(arr, n, i);
            
            // Trích xuất phần tử từ heap
            for (int i = n - 1; i >= 0; i--)
            {
                // Di chuyển root (max) đến cuối
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
                
                // Heapify root element
                Heapify(arr, i, 0);
            }
        }
        
        static void Heapify(int[] arr, int n, int i)
        {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            
            if (left < n && arr[left] > arr[largest])
                largest = left;
            
            if (right < n && arr[right] > arr[largest])
                largest = right;
            
            if (largest != i)
            {
                int swap = arr[i];
                arr[i] = arr[largest];
                arr[largest] = swap;
                
                Heapify(arr, n, largest);
            }
        }
        
        public static void Main()
        {
            int[] arr = { 55, 25, 89, 34, 12, 19, 78, 95, 1, 100 };
            int n = 10, i;
            
            Console.WriteLine("Heap Sort");
            Console.Write("Mảng ban đầu: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
            
            HeapSort(arr, 10);
            
            Console.Write("\nMảng đã sắp xếp: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

Kết quả

Heap Sort
Mảng ban đầu: 55 25 89 34 12 19 78 95 1 100
Mảng đã sắp xếp: 1 12 19 25 34 55 78 89 95 100

Giải thích thuật toán

1. Xây dựng heap (Build Heap): Từ nút không phải lá cuối cùng (n/2 - 1) lên gốc, gọi Heapify để tạo max heap.
2. Sắp xếp: Hoán đổi root (max) với phần tử cuối, giảm kích thước heap, gọi Heapify cho root.
3. Heapify: Đảm bảo tính chất max heap tại nút i. So sánh với con trái/phải, hoán đổi nếu cần và đệ quy.

Độ phức tạp: O(n log n) mọi trường hợp. Không gian O(1) (in-place). Không ổn định.