Hàng đợi ưu tiên và heap

/* Ba công thức, đúng cho mọi cây nhị phân hoàn chỉnh đánh số từ 0 */
cha(i)   = (i - 1) / 2
trai(i)  = 2 * i + 1
phai(i)  = 2 * i + 2

/* Kiểm với mảng 5 8 9 12 10 20 15:
     i = 0 (5)  -> trai = 1 (8),  phai = 2 (9)
     i = 1 (8)  -> trai = 3 (12), phai = 4 (10)
     i = 2 (9)  -> trai = 5 (20), phai = 6 (15)
     i = 4 (10) -> cha  = 1 (8)                                */

#ifndef HEAP_H
#define HEAP_H

#include <stddef.h>

/* Heap nhỏ nhất trên mảng động.
   Bất biến: với mọi i từ 1 tới n-1, data[(i-1)/2] <= data[i]     */
typedef struct {
    int   *data;
    size_t n;
    size_t suc_chua;
} MinHeap;

void   heap_khoi_tao(MinHeap *h);
void   heap_huy(MinHeap *h);
int    heap_rong(const MinHeap *h);
size_t heap_so_phan_tu(const MinHeap *h);
int    heap_push(MinHeap *h, int v);
int    heap_pop(MinHeap *h, int *out);
int    heap_xem(const MinHeap *h, int *out);
int    heap_dung(MinHeap *h, const int *a, size_t n);

#endif

#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include "heap.h"

void heap_khoi_tao(MinHeap *h)
{
    h->data     = NULL;
    h->n        = 0;
    h->suc_chua = 0;
}

void heap_huy(MinHeap *h)
{
    free(h->data);
    heap_khoi_tao(h);
}

int    heap_rong(const MinHeap *h)        { return h->n == 0; }
size_t heap_so_phan_tu(const MinHeap *h)  { return h->n; }

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

/* Đẩy phần tử ở vị trí i lên trên cho tới khi nó không nhỏ hơn cha.
   Chạy nhiều nhất log2(n) bước, vì mỗi bước lên một tầng. */
static void day_len(MinHeap *h, size_t i)
{
    while (i > 0) {
        size_t cha = (i - 1) / 2;

        if (h->data[cha] <= h->data[i]) break;      /* đã đúng chỗ */

        doi_cho(&h->data[cha], &h->data[i]);
        i = cha;
    }
}

static int bao_dam(MinHeap *h)
{
    if (h->n < h->suc_chua) return 0;

    size_t moi = h->suc_chua ? h->suc_chua * 2 : 8;

    if (moi > SIZE_MAX / sizeof *h->data) return -1;

    int *tam = realloc(h->data, moi * sizeof *tam);

    if (tam == NULL) return -1;

    h->data     = tam;
    h->suc_chua = moi;

    return 0;
}

/* Thêm một phần tử. O(log n). */
int heap_push(MinHeap *h, int v)
{
    if (bao_dam(h) != 0) return -1;

    h->data[h->n] = v;      /* đặt vào cuối, tức lá cuối cùng của tầng cuối */
    ++h->n;

    day_len(h, h->n - 1);

    return 0;
}

int heap_xem(const MinHeap *h, int *out)
{
    if (h->n == 0) return -1;

    if (out != NULL) *out = h->data[0];      /* gốc luôn là nhỏ nhất, O(1) */

    return 0;
}

/* Đẩy phần tử ở vị trí i xuống dưới cho tới khi nó không lớn hơn cả hai con.
   Chạy nhiều nhất log2(n) bước. */
static void day_xuong(MinHeap *h, size_t i)
{
    for (;;) {
        size_t trai = 2 * i + 1;
        size_t phai = 2 * i + 2;
        size_t nho  = i;

        if (trai < h->n && h->data[trai] < h->data[nho]) nho = trai;
        if (phai < h->n && h->data[phai] < h->data[nho]) nho = phai;

        if (nho == i) break;      /* đã nhỏ hơn hoặc bằng cả hai con */

        doi_cho(&h->data[i], &h->data[nho]);
        i = nho;
    }
}

/* Lấy phần tử nhỏ nhất ra. O(log n). */
int heap_pop(MinHeap *h, int *out)
{
    if (h->n == 0) return -1;

    if (out != NULL) *out = h->data[0];

    h->data[0] = h->data[h->n - 1];      /* đưa lá cuối lên gốc */
    --h->n;

    if (h->n > 0) day_xuong(h, 0);

    return 0;
}

#include <stdio.h>

#include "heap.h"

int main(void)
{
    MinHeap h;
    int     v;

    heap_khoi_tao(&h);

    int nguon[] = { 9, 4, 7, 1, 8, 20, 3 };

    for (size_t i = 0; i < sizeof nguon / sizeof nguon[0]; ++i)
        if (heap_push(&h, nguon[i]) != 0) { heap_huy(&h); return 1; }

    printf("so phan tu: %zu\n", heap_so_phan_tu(&h));

    heap_xem(&h, &v);
    printf("nho nhat  : %d\n", v);

    printf("lay het   : ");

    while (heap_pop(&h, &v) == 0) printf("%d ", v);

    printf("\n");

    heap_huy(&h);

    return 0;
}

/* Dựng heap từ mảng a có n phần tử. O(n), không phải O(n log n). */
int heap_dung(MinHeap *h, const int *a, size_t n)
{
    if (n > SIZE_MAX / sizeof *h->data) return -1;

    int *tam = malloc(n ? n * sizeof *tam : 1);

    if (tam == NULL) return -1;

    memcpy(tam, a, n * sizeof *tam);

    free(h->data);
    h->data     = tam;
    h->n        = n;
    h->suc_chua = n;

    /* Nút cuối cùng không phải lá là cha của nút cuối, tức (n-2)/2.
       Viết dưới dạng i = n/2 rồi đếm lùi để tránh trừ với size_t. */
    for (size_t i = n / 2; i-- > 0; )
        day_xuong(h, i);

    return 0;
}

/* Giữ một heap NHỎ NHẤT kích thước đúng K.
   Gốc của nó là phần tử nhỏ nhất trong K phần tử lớn nhất đã gặp.
   Gặp số lớn hơn gốc thì thay gốc rồi đẩy xuống.

   O(n log K) thời gian, O(K) bộ nhớ.
   So với sắp xếp cả mảng: O(n log n) và O(n).                    */
int top_k(const int *a, size_t n, size_t k, int *ra)
{
    if (k == 0 || k > n) return -1;

    MinHeap h;

    heap_khoi_tao(&h);

    if (heap_dung(&h, a, k) != 0) return -1;      /* K phần tử đầu */

    for (size_t i = k; i < n; ++i) {
        if (a[i] > h.data[0]) {
            h.data[0] = a[i];
            day_xuong(&h, 0);
        }
    }

    for (size_t i = 0; i < k; ++i) ra[i] = h.data[i];

    heap_huy(&h);

    return 0;
}