Heap sort

/* Hai giai đoạn:

     Giai đoạn 1: dựng max heap từ mảng bất kỳ.       O(n)
     Giai đoạn 2: rút gốc n-1 lần.                    O(n log n)

   Tổng: O(n log n) trong MỌI trường hợp,
         và KHÔNG dùng byte bộ nhớ phụ nào.

   Dùng MAX heap chứ không phải min heap, vì ta muốn
   phần tử lớn nhất đi về CUỐI mảng.                            */

#include <stddef.h>

static void doi_cho(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* Đẩy phần tử ở vị trí i xuống cho tới khi nó lớn hơn hoặc bằng cả hai con.
   Chỉ xét vùng a[0..n), tức n là kích thước heap HIỆN TẠI.
   Chạy nhiều nhất log2(n) bước. */
static void day_xuong(int *a, size_t i, size_t n)
{
    for (;;) {
        size_t trai = 2 * i + 1;
        size_t phai = 2 * i + 2;
        size_t lon  = i;

        if (trai < n && a[trai] > a[lon]) lon = trai;
        if (phai < n && a[phai] > a[lon]) lon = phai;

        if (lon == i) break;      /* đã đúng chỗ */

        doi_cho(&a[i], &a[lon]);
        i = lon;
    }
}

/* Mỗi phép đổi chỗ tốn 3 phép gán. Dịch thì chỉ tốn 1. */
static void day_xuong_dich(int *a, size_t i, size_t n)
{
    int    khoa = a[i];
    size_t con;

    while ((con = 2 * i + 1) < n) {
        if (con + 1 < n && a[con + 1] > a[con]) ++con;   /* con lớn hơn */

        if (a[con] <= khoa) break;

        a[i] = a[con];      /* dịch con lên, chưa ghi khoa */
        i    = con;
    }

    a[i] = khoa;            /* ghi khoa vào chỗ cuối cùng */
}

/* Giai đoạn 1: biến mảng thành max heap.
   Đi từ nút không phải lá cuối cùng lên gốc.
   Chi phí O(n), không phải O(n log n). Bài 23.4 đã chứng minh. */
static void dung_heap(int *a, size_t n)
{
    for (size_t i = n / 2; i-- > 0; )
        day_xuong(a, i, n);
}

void heap_sort(int *a, size_t n)
{
    if (n < 2) return;

    dung_heap(a, n);                    /* giai đoạn 1: O(n) */

    for (size_t i = n; i-- > 1; ) {     /* giai đoạn 2: O(n log n) */
        doi_cho(&a[0], &a[i]);          /* lớn nhất về cuối vùng heap */
        day_xuong(a, 0, i);             /* vùng heap thu nhỏ còn i */
    }
}

#include <stdio.h>

void heap_sort(int *a, size_t n);

int main(void)
{
    int    a[] = { 9, 4, 7, 1, 8, 20, 3 };
    size_t n   = sizeof a / sizeof a[0];

    printf("truoc: ");

    for (size_t i = 0; i < n; ++i) printf("%d ", a[i]);

    heap_sort(a, n);

    printf("\nsau  : ");

    for (size_t i = 0; i < n; ++i) printf("%d ", a[i]);

    printf("\n");

    return 0;
}

/* k phần tử lớn nhất, đã sắp, nằm ở cuối mảng.
   O(n) dựng heap, cộng O(k log n) rút gốc. */
void k_lon_nhat(int *a, size_t n, size_t k)
{
    if (n < 2 || k == 0) return;

    if (k > n) k = n;

    dung_heap(a, n);

    for (size_t i = n; i-- > n - k; ) {
        doi_cho(&a[0], &a[i]);
        day_xuong(a, 0, i);
    }

    /* a[n-k..n) là k phần tử lớn nhất, đã sắp tăng dần. */
}