Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 55.330 phút đọc

Heap, cây và bảng băm

Sau bài này bạn sẽ làm được

  • Cài hàng đợi ưu tiên bằng heap nhị phân trên mảng
  • Cài cây tìm kiếm nhị phân với hàm so sánh mang ngữ cảnh
  • Cài bảng băm với dò tuyến tính và hệ số tải
  • Chọn đúng container cho một bài toán cụ thể

Ba container còn lại, và mỗi cái mạnh ở một chỗ hai cái kia không làm được: heap cho phần tử lớn nhất, cây cho duyệt theo thứ tự, bảng băm cho tra cứu O(1).

#Heap: hàng đợi ưu tiên trên mảng

heap.c, cấu trúc và push
struct Heap {
    void  *d;
    size_t n, cap, esz;
    CmpFn  cmp;          /* luu ngay trong heap, khac Vector */
    void  *ctx;
};

Heap *heap_new(size_t esz, CmpFn cmp, void *ctx) {
    if (esz == 0 || cmp == NULL) return NULL;
    ...
    h->cmp = cmp;
    h->ctx = ctx;
    return h;
}

int heap_push(Heap *h, const void *pt) {
    if (h == NULL || pt == NULL) return -1;

    if (h->n == h->cap) { ... mo rong nhu vector ... }

    memcpy(o(h, h->n), pt, h->esz);
    ++h->n;

    /* NOI LEN: doi cho voi cha cho toi khi dung cho */
    for (size_t i = h->n - 1; i > 0; ) {
        size_t cha = (i - 1) / 2;
        if (h->cmp(o(h, i), o(h, cha), h->ctx) <= 0) break;
        doi_cho(o(h, i), o(h, cha), h->esz);
        i = cha;
    }

    return 0;
}
heap_pop
int heap_pop(Heap *h, void *ra) {
    if (h == NULL || h->n == 0) return -1;

    if (ra != NULL) memcpy(ra, o(h, 0), h->esz);   /* goc la lon nhat */

    --h->n;
    if (h->n > 0) memcpy(o(h, 0), o(h, h->n), h->esz);  /* dua cuoi len goc */

    /* CHIM XUONG: doi cho voi con lon hon cho toi khi dung cho */
    for (size_t i = 0; ; ) {
        size_t lon = i, t = 2 * i + 1, p = t + 1;

        if (t < h->n && h->cmp(o(h, t), o(h, lon), h->ctx) > 0) lon = t;
        if (p < h->n && h->cmp(o(h, p), o(h, lon), h->ctx) > 0) lon = p;
        if (lon == i) break;

        doi_cho(o(h, i), o(h, lon), h->esz);
        i = lon;
    }

    return 0;
}
Thao tácĐộ phức tạpGhi chú
heap_pushO(log n)Nổi lên tối đa log n tầng
heap_popO(log n)Chìm xuống tối đa log n tầng
heap_peekO(1)Chỉ đọc phần tử ở chỉ số 0
Dựng heap từ n phần tửO(n)Không phải O(n log n)
Tìm một phần tử bất kỳO(n)Heap không phải cấu trúc tra cứu
terminal
# Kiểm thử: pop ra phải theo thứ tự giảm dần
./chay_thu.exe
[vector]
[list]
[heap]
[tree]
[hashmap]

3121 kiem tra, 0 hong
Bài kiểm thử quan trọng nhất của heap
int ds[] = { 5, 3, 9, 1, 7, 2, 8 };
for (size_t i = 0; i < sizeof ds / sizeof ds[0]; ++i)
    KIEM(heap_push(h, &ds[i]) == 0);

KIEM(*(int *)heap_peek(h) == 9);

/* Lay ra phai theo thu tu giam dan */
int truoc = 1000, ra;
while (heap_pop(h, &ra) == 0) {
    KIEM(ra <= truoc);
    truoc = ra;
}

/* Bai nay kiem tra BAT BIEN chu khong kiem tra tung gia tri.
   No dung voi moi du lieu vao, nen ban co the chay no voi
   mot nghin so ngau nhien va van dung.

   Do la cach kiem thu cau truc du lieu: kiem tra bat bien,
   khong kiem tra ket qua cu the. */

#Cây tìm kiếm nhị phân

tree.c, chèn dùng con trỏ tới con trỏ
typedef struct TNut {
    struct TNut *trai, *phai;
    /* du lieu ngay sau, nhu list */
} TNut;

int tree_insert(Tree *t, const void *pt) {
    if (t == NULL || pt == NULL) return -1;

    TNut **cho = &t->goc;              /* con tro toi CON TRO */

    while (*cho != NULL) {
        int c = t->cmp(pt, du_lieu(*cho), t->ctx);
        if (c == 0) return -1;         /* da ton tai */
        cho = (c < 0) ? &(*cho)->trai : &(*cho)->phai;
    }

    TNut *n = malloc(sizeof(TNut) + t->esz);
    if (n == NULL) return -1;

    n->trai = n->phai = NULL;
    memcpy(du_lieu(n), pt, t->esz);

    *cho = n;                          /* gan vao dung cho, du la goc
                                          hay la con cua mot nut */
    ++t->n;
    return 0;
}
Con trỏ thường
/* Khong dung con tro toi con tro: phai xu ly goc rieng */

int tree_insert(Tree *t, const void *pt) {
    TNut *n = tao_nut(t, pt);
    if (n == NULL) return -1;

    if (t->goc == NULL) {              /* truong hop dac biet */
        t->goc = n;
        ++t->n;
        return 0;
    }

    TNut *p = t->goc;
    for (;;) {
        int c = t->cmp(pt, du_lieu(p), t->ctx);
        if (c == 0) { free(n); return -1; }

        if (c < 0) {
            if (p->trai == NULL) { p->trai = n; break; }
            p = p->trai;
        } else {
            if (p->phai == NULL) { p->phai = n; break; }
            p = p->phai;
        }
    }
    ...
}

/* Ba nhanh dac biet, va mot loi tinh vi: nut da cap phat TRUOC
   khi biet khoa co trung hay khong, nen phai nho free(n). */
Con trỏ tới con trỏ
TNut **cho = &t->goc;

while (*cho != NULL) {
    int c = t->cmp(pt, du_lieu(*cho), t->ctx);
    if (c == 0) return -1;             /* tra ve TRUOC khi cap phat */
    cho = (c < 0) ? &(*cho)->trai : &(*cho)->phai;
}

TNut *n = malloc(sizeof(TNut) + t->esz);
if (n == NULL) return -1;
...
*cho = n;

/* Mot vong lap, khong nhanh dac biet nao.
   "cho" tro toi CHO CAN GHI, du do la t->goc hay p->trai hay p->phai.

   Va cap phat SAU khi da biet chac se chen, nen khong bao gio
   phai free mot nut vua tao. */
Duyệt theo thứ tự, đệ quy
static void duyet(TNut *n, ApplyFn f, void *ctx) {
    if (n == NULL) return;
    duyet(n->trai, f, ctx);
    f(du_lieu(n), ctx);
    duyet(n->phai, f, ctx);
}

void tree_inorder(const Tree *t, ApplyFn f, void *ctx) {
    if (t == NULL || f == NULL) return;
    duyet(t->goc, f, ctx);
}

/* De quy o day CHAP NHAN DUOC vi:
     - do sau la O(log n) voi cay can bang, tuc khoang 20 voi
       mot trieu phan tu
     - moi khung ngan xep rat nho

   NHUNG voi cay khong can bang va du lieu sap xep san thi do sau
   la O(n), va mot trieu phan tu se tran ngan xep. Bai 34.5.

   Ban lap, dung mot ngan xep tuong minh: */

void tree_inorder_lap(const Tree *t, ApplyFn f, void *ctx) {
    TNut *ngan_xep[64];              /* du cho cay can bang toi 2^64 */
    int   dinh = 0;
    TNut *n = t->goc;

    while (n != NULL || dinh > 0) {
        while (n != NULL) {
            if (dinh == 64) return;  /* cay qua sau, tu choi */
            ngan_xep[dinh++] = n;
            n = n->trai;
        }
        n = ngan_xep[--dinh];
        f(du_lieu(n), ctx);
        n = n->phai;
    }
}

#Bảng băm với dò tuyến tính

hashmap.c, cấu trúc
enum { O_TRONG = 0, O_DUNG = 1, O_XOA = 2 };

struct HashMap {
    unsigned char *o;      /* trang thai tung o: TRONG, DUNG, hoac XOA */
    void          *khoa;   /* mang khoa, song song voi o[] */
    void          *gt;     /* mang gia tri, song song */
    size_t         cap, n, xoa;
    size_t         ksz, vsz;
    HashFn         bam;
    EqFn           bang;
    void          *ctx;
};
Tìm ô: cốt lõi của cả bảng băm
static size_t tim_o(const HashMap *m, const void *khoa, int *thay) {
    size_t i = m->bam(khoa, m->ctx) & (m->cap - 1);   /* cap la luy thua 2 */
    size_t dau_xoa = m->cap;                          /* chua thay o XOA nao */

    for (size_t b = 0; b < m->cap; ++b) {
        if (m->o[i] == O_TRONG) {
            *thay = 0;
            /* uu tien tai su dung o XOA neu da gap */
            return (dau_xoa != m->cap) ? dau_xoa : i;
        }
        if (m->o[i] == O_XOA) {
            if (dau_xoa == m->cap) dau_xoa = i;        /* ghi nho o dau tien */
        } else if (m->bang(k_o(m, i), khoa, m->ctx)) {
            *thay = 1;
            return i;                                  /* tim thay khoa */
        }
        i = (i + 1) & (m->cap - 1);                    /* do tuyen tinh */
    }

    *thay = 0;
    return (dau_xoa != m->cap) ? dau_xoa : m->cap;     /* bang day */
}
Bài kiểm thử bắt được đúng lỗi đó
/* Them 1000 khoa */
for (int i = 0; i < 1000; ++i) { int gt = i * i; hm_put(m, &i, &gt); }

/* Xoa mot nua */
for (int i = 0; i < 500; ++i) hm_remove(m, &i, NULL);

/* Nua con lai PHAI van tim duoc */
for (int i = 500; i < 1000; ++i) {
    int *gt = hm_get(m, &i);
    KIEM(gt != NULL && *gt == i * i);
}

/* Neu ban cai o XOA sai thi bai nay hong ngay, va no hong
   voi hang tram khoa chu khong phai mot, nen rat de nhan ra. */

#Hàm băm

Hai hàm băm có sẵn
/* FNV-1a cho chuoi: don gian, du tot cho bang bam thong thuong */

size_t cds_bam_chuoi(const void *khoa, void *ctx) {
    (void)ctx;
    const char *s = *(const char *const *)khoa;
    size_t h = 14695981039346656037ULL;      /* hat FNV */
    for (; *s; ++s) {
        h ^= (unsigned char)*s;               /* XOR byte */
        h *= 1099511628211ULL;                /* nhan so nguyen to */
    }
    return h;
}

/* Tron bit kieu MurmurHash cho so nguyen */

size_t cds_bam_int(const void *khoa, void *ctx) {
    (void)ctx;
    uint64_t x = (uint64_t)(*(const int *)khoa);
    x ^= x >> 33; x *= 0xff51afd7ed558ccdULL;
    x ^= x >> 33; x *= 0xc4ceb9fe1a85ec53ULL;
    x ^= x >> 33;
    return (size_t)x;
}
Băm một struct: phải băm từng trường
typedef struct { int ma; char lop[8]; } Khoa;

/* SAI: bam ca struct */
size_t bam_sai(const void *k, void *ctx) {
    (void)ctx;
    return bam_byte(k, sizeof(Khoa));       /* PHAN DEM la rac! */
}

/* Bai 53.1 da noi: byte dem khong co gia tri xac dinh.
   Hai struct cung noi dung co the bam ra hai so khac nhau. */

/* DUNG: bam tung truong */
size_t bam_dung(const void *k, void *ctx) {
    (void)ctx;
    const Khoa *x = k;
    size_t h = 14695981039346656037ULL;

    h ^= (size_t)x->ma;  h *= 1099511628211ULL;
    for (int i = 0; i < 8; ++i) {
        h ^= (unsigned char)x->lop[i];
        h *= 1099511628211ULL;
    }
    return h;
}

/* Va ham so sanh bang cung phai so tung truong, khong dung memcmp,
   cung mot ly do. */

#Chọn container nào

Thao tácVectorListHeapTreeHashMap
Tra cứu theo khóaO(n)O(n)O(n)O(log n)O(1)
Truy cập theo chỉ sốO(1)O(n)O(1)KhôngKhông
ThêmO(1)O(1)O(log n)O(log n)O(1)
XóaO(n)O(1)O(log n)O(log n)O(1)
Lấy phần tử lớn nhấtO(n)O(n)O(1)O(log n)O(n)
Duyệt theo thứ tựCần sắp trướcKhôngKhôngO(n)Không
Bộ nhớ phụ mỗi phần tử016 byte016 byte1 byte cộng chỗ trống
Thân thiện bộ nhớ đệmRất tốtKémTốtKémTốt

Tự làm thử

  1. Cài heap và kiểm tra bất biến bằng cách pop ra một nghìn số ngẫu nhiên.
  2. Đổi tree_insert sang bản không dùng con trỏ tới con trỏ và so số dòng.
  3. Chèn 1000 số tăng dần vào cây và đo độ sâu.
  4. Cài bảng băm, xóa một nửa số khóa, rồi xác nhận nửa còn lại vẫn tìm được.
  5. Dùng hàm băm trả về thẳng giá trị số và đếm số va chạm.
  6. Đo tra cứu trên vector và trên bảng băm với 10, 100, 1000 và 100000 phần tử.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

  • Heap lưu cây nhị phân trong mảng phẳng: con ở 2i+1 và 2i+2, cha ở (i-1)/2. Dựng heap là O(n).
  • Hàm so sánh lưu trong heap, cây và bảng băm vì chúng có bất biến phụ thuộc nó; vector thì nhận từng lời gọi.
  • Con trỏ tới con trỏ xóa bỏ mọi trường hợp đặc biệt trong cấu trúc liên kết, và cho phép cấp phát sau khi đã chắc chắn.
  • Ô XÓA phải khác ô TRỐNG, nếu không việc xóa một khóa làm mất các khóa va chạm phía sau nó.
  • Hàm băm phải trộn bit; trả về thẳng giá trị số biến bảng băm thành danh sách liên kết với khóa có bước nhảy đều.