Heap Sort ใน C#

ภาพรวม

Heap Sort เป็นอัลกอริทึมการจัดเรียงที่ใช้โครงสร้างข้อมูล Heap (โดยเฉพาะ Max-Heap) ทำงานโดย:

1. สร้าง Max-Heap จากอาร์เรย์ (องค์ประกอบมากที่สุดอยู่ราก)
2. สลับราก (ค่ามากที่สุด) กับองค์ประกอบสุดท้าย
3. ลดขนาด Heap ลง 1 และเรียก Heapify เพื่อฟื้นฟูคุณสมบัติ Heap
4. ซ้ำจนกว่า Heap จะเหลือขนาด 1

Heap Sort มีความซับซ้อนเวลา O(n log n) ในทุกกรณี และเป็น In-place (พื้นที่ O(1))

ตัวอย่างโปรแกรม

using System;

namespace HeapSortDemo
{
    public class Example
    {
        // Heapify: ฟื้นฟูคุณสมบัติ Max-Heap ที่โหนด i
        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;
            
            // หากลูกมากกว่าราก ให้สลับและ Heapify ต่อที่ลูก
            if (largest != i)
            {
                int swap = arr[i];
                arr[i] = arr[largest];
                arr[largest] = swap;
                
                Heapify(arr, n, largest); // Recursive call
            }
        }
        
        // Heap Sort หลัก
        static void HeapSort(int[] arr, int n)
        {
            // 1. Build Max-Heap (เริ่มจาก non-leaf nodes)
            for (int i = n / 2 - 1; i >= 0; i--)
                Heapify(arr, n, i);
            
            // 2. Extract elements ทีละตัว
            for (int i = n - 1; i >= 0; i--)
            {
                // สลับราก (max) กับตัวสุดท้าย
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
                
                // Heapify รากใหม่บน Heap ขนาด i
                Heapify(arr, i, 0);
            }
        }
        
        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("อาร์เรย์เริ่มต้น: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
            
            HeapSort(arr, 10);
            
            Console.Write("\nอาร์เรย์ที่จัดเรียงแล้ว: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

ผลลัพธ์

Heap Sort
อาร์เรย์เริ่มต้น: 55 25 89 34 12 19 78 95 1 100
อาร์เรย์ที่จัดเรียงแล้ว: 1 12 19 25 34 55 78 89 95 100

การทำงานแบบทีละขั้นตอน

1. Build Heap (สร้าง Max-Heap)

for (int i = n / 2 - 1; i >= 0; i--)
    Heapify(arr, n, i);

เริ่มจากโหนด non-leaf สุดท้าย (n/2 - 1) ย้อนกลับไปราก เรียก Heapify เพื่อให้ทุกโหนดเป็น Max-Heap

2. Sorting Phase (ดึงค่ามากที่สุด)

for (int i = n - 1; i >= 0; i--)
{
    Swap(arr[0], arr[i]);   // ย้าย max ไปท้าย
    Heapify(arr, i, 0);     // ฟื้นฟู heap ขนาด i
}

3. Heapify (ฟื้นฟูคุณสมบัติ Heap)

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)
{
    Swap(arr[i], arr[largest]);
    Heapify(arr, n, largest); // ดำเนินต่อไปล่าง
}

ความซับซ้อน (Complexity)

ข้อสังเกตสำคัญ

• ไม่เสถียร (Unstable) - ค่าเท่ากันอาจสลับตำแหน่ง
• In-place: ไม่ต้องการอาร์เรย์ชั่วคราว
• ประสิทธิภาพคงที่ O(n log n) - ไม่มีกรณีแย่ที่สุดเหมือน Quick Sort
• Cache performance ไม่ดีเท่า Merge/Quick Sort (การเข้าถึงหน่วยความจำกระโดด)
• ใช้ในระบบ Real-time ที่ต้องการเวลาสูงสุดที่รับประกันได้
• ใน .NET ใช้ Array.Sort() (Introsort) แทน ซึ่งเร็วกว่าในทางปฏิบัติ

การเปรียบเทียบอัลกอริทึมจัดเรียงหลัก