Tổng quan
Đống nhị phân cực đại (Binary Max-Heap) là một cây nhị phân đầy đủ được lưu gọn trong mảng, trong đó mỗi nút cha lớn hơn hoặc bằng các con của nó. Trật tự này giữ phần tử lớn nhất luôn ở gốc, sẵn sàng đọc trong O(1).
Vì cây đầy đủ, một nút ở chỉ số i tìm các con tại 2i+1 và 2i+2, nên không cần con trỏ. Đống dựa trên mảng này là cách cài đặt chuẩn cho hàng đợi ưu tiên.
Heap (Đống nhị phân) hoạt động thế nào?
- Chèn thêm giá trị mới vào cuối, rồi đẩy lên: hoán đổi với cha khi nó lớn hơn.
- Lấy phần tử lớn nhất bỏ gốc, chuyển phần tử cuối lên đỉnh, rồi đẩy xuống qua nút con lớn hơn.
- Việc đẩy lên hay đẩy xuống chạm tối đa một nút mỗi tầng, nên tốn O(log n).
- Xây đống từ mảng chưa sắp bằng cách đẩy xuống từ nút cha cuối tới gốc, chỉ tốn O(n).
Khi nào nên dùng?
- Cài đặt hàng đợi ưu tiên, khi phần tử có ưu tiên cao nhất phải được xử lý trước.
- Bộ máy bên trong Heap Sort và biên tìm kiếm của thuật toán đường đi ngắn nhất Dijkstra và A*.
- Các bài toán luồng như tìm k phần tử lớn nhất mà không cần sắp toàn bộ.
Phân tích độ phức tạp
Chèn và lấy phần tử lớn nhất đều chạy O(log n) vì chúng đi dọc một đường từ gốc tới lá. Đọc giá trị lớn nhất là O(1). Xây đống từ n phần tử tốn O(n), không phải O(n log n), nhờ cách xây bằng đẩy xuống. Bộ nhớ là O(n).
Câu hỏi thường gặp
Vì sao xây đống là O(n) chứ không phải O(n log n)?
Phần lớn nút nằm gần đáy và chỉ đẩy xuống vài tầng; cộng công việc trên mọi tầng tạo thành một chuỗi hội tụ có tổng O(n), chứ không phải n lần chèn O(log n) độc lập.
Đống khác cây tìm kiếm nhị phân ở điểm nào?
Đống chỉ đảm bảo trật tự cha-con, nên tìm giá trị lớn nhất nhanh nhưng không tìm kiếm giá trị bất kỳ hiệu quả; cây tìm kiếm nhị phân giữ trật tự trái-phải đầy đủ để tra cứu O(log n).