Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Heap là cây, không phải mảng
Heap là cây nhị phân mà mỗi nút luôn lớn hơn hoặc bằng hai con của nó. Hệ quả: phần tử lớn nhất luôn nằm ở đỉnh, và bạn lấy được nó ngay không cần tìm.
Đỉnh 9, hai con 7 và 5, bốn cháu 3 4 2 1 — cha luôn lớn hơn con
Cây đó nằm sẵn trong mảng
- Mảng9 7 5 3 4 2 1 — bảy ô liên tiếp, không con trỏ nào
- ĐỉnhVị trí 0 là số 9, chính là gốc của cây
- Công thứcCon của vị trí i nằm ở 2i+1 và 2i+2
- Kiểm lạiCon của vị trí 0 là vị trí 1 và 2, tức 7 và 5
Lấy dần đỉnh xuống cuối mảng
Đổi chỗ đỉnh với phần tử cuối, coi như phần tử đó đã xong, rồi kéo phần tử mới lên đỉnh xuống đúng tầng của nó. Lặp n lần, mỗi lần tốn log n bước.
Vì sao introsort giữ heap sort
Nó là thuật toán duy nhất vừa đảm bảo n log n trong mọi trường hợp, vừa không cần bộ nhớ phụ. Khi quick sort đệ quy quá sâu, introsort đổi sang nó để chặn n².
Học heap dùng được nhiều hơn
Hàng đợi ưu tiên gần như luôn cài bằng heap, và bạn gặp nó nhiều hơn hẳn việc tự viết hàm sắp xếp: lập lịch job, tìm đường, gộp nhiều luồng log theo thời gian.
Heap sort: được gì, mất gì
Ưu điểm
n log n cả ở trường hợp xấu nhất
Sắp xếp tại chỗ, bộ nhớ phụ O(1)
Không đệ quy nên không lo tràn ngăn xếp
Nhược điểm
Chậm hơn quick sort thực tế vì cache miss
Không ổn định
Phải hiểu heap trước khi hiểu sắp xếp
Lưu lại để chạy tay sau
Loạt bài thuật toán sắp xếp cho dev Việt Nam.
