Min-Heap — biểu diễn mảng + cây


Cây (cha-con)

Mảng cùng dữ liệu

Min-heap: mỗi node ≤ con. Cha của i là (i-1)/2; con 2i+1 và 2i+2.

Tổ chức bộ nhớ — Cách 2: Array-based (README §2)

Heap lưu liên tiếp trong RAM, mỗi int32 = 4 byte. Click vào một ô để xem cha, con trái, con phải cùng cách tính bit của index.

Click vào ô bất kỳ ở trên — viz sẽ highlight cha/con và giải thích công thức bit.
Array-based (cách này)
n × 4 byte liên tiếp. 0% overhead, cache-friendly tuyệt đối.
Cho 7 phần tử: 28 byte.
Pointer-based (Lesson 6, cách 1)
n × 24 byte rải rác. 83% overhead, mỗi xuống tầng = 1 cache miss.
Cho 7 phần tử: 168 byte.

Top-K trending stream (README §6.2 / §7.4)

Min-heap size K = "phòng VIP". Gốc heap = người gác cửa (nhỏ nhất trong K đang giữ). Mỗi tag mới: nếu count > người gác cửa → đá gác cửa, cho vào; nếu không → bỏ. Bộ nhớ luôn chỉ O(K).

Stream còn lại:
Heap (size ≤ K) — ô đầu là người gác cửa:
Nhấn "Nạp tag tiếp theo" để mô phỏng. Cuối stream, heap chứa đúng top-K.