Đống (Heap)

Cấu trúc dữ liệu Đống (Heap) là một cấu trúc dữ liệu cây nhị phân đặc biệt, thường được sử dụng để triển khai hàng đợi ưu tiên (priority queue). Đối với Đống, có hai loại chính là Đống tối đa (max heap) và Đống tối thiểu (min heap), phụ thuộc vào thứ tự giá trị của các nút.

Cấu trúc của Đống

Đống được biểu diễn dưới dạng cây nhị phân có các đặc điểm sau:

Cây nhị phân đầy đủ (complete binary tree): Các nút được sắp xếp từ trên xuống dưới, từ trái sang phải, và mọi mức (level) của cây (trừ có thể là mức cuối cùng) được đầy đủ.
Điều kiện Đống (Heap property):
- Đống tối đa (max heap): Giá trị của nút cha luôn lớn hơn hoặc bằng giá trị của các nút con.
- Đống tối thiểu (min heap): Giá trị của nút cha luôn nhỏ hơn hoặc bằng giá trị của các nút con.

Thao tác cơ bản trên Đống

Các thao tác cơ bản trên Đống bao gồm:

Thêm phần tử (insert):
- Thêm phần tử mới vào vị trí cuối cùng của cây nhị phân.
- Sau đó, điều chỉnh lại Đống bằng việc sử dụng phép đổi chỗ (heapify up) để đảm bảo cây vẫn thỏa mãn điều kiện Đống.
Xóa phần tử gốc (remove root):
- Loại bỏ phần tử gốc của Đống (là phần tử có giá trị cao nhất trong max heap hoặc thấp nhất trong min heap).
- Thay thế phần tử gốc bằng phần tử cuối cùng của cây nhị phân.
- Sau đó, điều chỉnh lại Đống bằng phép đổi chỗ (heapify down) để tái cân bằng cây và duy trì điều kiện Đống.
Truy xuất phần tử gốc (peek root):
- Truy xuất giá trị của phần tử gốc mà không loại bỏ nó khỏi Đống.

Ứng dụng của Đống

Đống được sử dụng trong nhiều ứng dụng quan trọng như:

Heap Sort: Một thuật toán sắp xếp dựa trên Đống để sắp xếp một mảng các phần tử.
Hàng đợi ưu tiên (Priority Queue): Được triển khai bằng Đống để quản lý và truy xuất các phần tử theo mức ưu tiên (lớn nhất hoặc nhỏ nhất).
Thuật toán Prim: Dùng để tìm cây khung nhỏ nhất trong đồ thị vô hướng, nơi mà Đống giúp duy trì các đỉnh còn lại mà không thuộc cây khung.
Thuật toán Dijkstra: Sử dụng Đống để duy trì và cập nhật các khoảng cách ngắn nhất từ một đỉnh đến tất cả các đỉnh khác trong đồ thị.

Tóm lại, Đống là một cấu trúc dữ liệu hiệu quả cho việc quản lý ưu tiên và thực hiện các thao tác cơ bản như thêm, xóa, và truy xuất phần tử với độ phức tạp thời gian logarit.