Heap Sort (การจัดเรียงแบบฮีป)

Heap Sort ใช้โครงสร้างข้อมูล Heap (Binary Heap) ซึ่งเป็น Complete Binary Tree ที่มีคุณสมบัติ: Max-Heap (พาเรนต์ ≥ ลูก) หรือ Min-Heap (พาเรนต์ ≤ ลูก)

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

แนวคิดการทำงาน (Max-Heap)

1. Build Max-Heap: จัดเรียงอาเรย์ให้เป็น Max-Heap (รูท = ค่าสูงสุด)
2. Extract Max: สลับรูท (ค่าสูงสุด) กับองค์ประกอบสุดท้าย ลดขนาดฮีปลง 1
3. Heapify: ปรับโครงสร้างฮีปใหม่จากรูทลงมา
4. ทำซ้ำขั้นตอน 2-3 จนฮีปเหลือขนาด 1

ตัวอย่างข้อมูล

Input:  30 8 99 11 24 39
Output: 8 11 24 30 39 99

อัลกอริทึม (Pseudocode)

heapify(array, n, i)  // i = index ของโหนดที่จะ heapify
  largest = i
  left = 2*i + 1
  right = 2*i + 2
  if left < n AND array[left] > array[largest]: largest = left
  if right < n AND array[right] > array[largest]: largest = right
  if largest != i:
    swap(array[i], array[largest])
    heapify(array, n, largest)

heapSort(array, n)
  // Build heap (เริ่มจาก parent สุดท้าย)
  for i = n/2 - 1 down to 0:
    heapify(array, n, i)

  // Extract elements
  for i = n-1 down to 1:
    swap(array[0], array[i])  // ย้าย max ไปท้าย
    heapify(array, i, 0)      // heapify root บน heap ที่เล็กลง

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

void heapify(int *array, int n, int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < n && array[left] > array[largest]) largest = left;
    if (right < n && array[right] > array[largest]) largest = right;

    if (largest != i) {
        swap(array[i], array[largest]);
        heapify(array, n, largest);
    }
}

void heapSort(int *array, int n) {
    // Build max heap
    for (int i = n/2 - 1; i >= 0; i--)
        heapify(array, n, i);

    // Extract elements
    for (int i = n-1; i > 0; i--) {
        swap(array[0], array[i]);
        heapify(array, i, 0);
    }
}

void display(int *array, int size) {
    for (int i = 0; i < size; i++) cout << array[i] << " ";
    cout << endl;
}

int main() {
    int n; cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) cin >> arr[i];
    cout << "Before: "; display(arr, n);
    heapSort(arr, n);
    cout << "After: "; display(arr, n);
}

คุณสมบัติสำคัญ

• In-place: O(1) extra space
• Not Stable: ไม่รักษาลำดับค่าเท่ากัน
• Guaranteed O(n log n): ไม่มี Worst case แย่
• ใช้ใน Embedded Systems / Real-time ที่ต้องการเวลาคงที่

ดัชนีในอาเรย์ (0-based indexing)

• Parent of i: (i-1)/2
• Left child: 2*i + 1
• Right child: 2*i + 2