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à gì
Heap là một cây nhị phân, mỗi nút có nhiều nhất hai con. Điều kiện duy nhất: giá trị ở mỗi nút luôn lớn hơn hoặc bằng hai con của nó. Nhờ vậy số lớn nhất luôn nằm ở đỉnh.
Bằng cũng được, nên dữ liệu trùng giá trị vẫn hợp lệ
Cây này nằm trong một mảng
Không cần con trỏ. Nút ở vị trí i có hai con ở 2i+1 và 2i+2. Cây và mảng là cùng một dữ liệu, chỉ là hai cách nhìn. Đó là lý do heap sort không cần bộ nhớ phụ.
Đếm từ 0
Sắp xếp bằng heap
- Dựng heapBiến cả mảng thành heap một lần
- Lấy đỉnhĐỉnh là số lớn nhất, đưa về cuối mảng
- Sift-downKéo phần tử mới ở đỉnh xuống đúng tầng
- Thu hẹpBỏ phần cuối ra, lặp lại với phần còn lại
Vì sao thư viện vẫn giữ heap sort
Introsort bắt đầu bằng quick sort. Khi đệ quy quá sâu, nó đổi sang heap sort. Heap sort đảm bảo n log n trong mọi trường hợp, nên nó là cái chặn cho trường hợp xấu nhất.
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ật, vì nhảy bộ nhớ
Không ổn định
Phải hiểu heap trước, khó đọc hơn hẳn
Bài cuối: counting sort
Thuật toán không so sánh gì cả, và đi vòng qua được giới hạn n log n.
