Cấu trúc đống và ứng dụng

Trong khoa học máy tính, đống (tiếng Anh: heap) là một cấu trúc dữ liệu dựa trên cây thỏa mãn tính chất đống: nếu B là nút con của A thì khóa(A)≥khóa(B). Một hệ quả của tính chất này là khóa lớn nhất luôn nằm ở nút gốc. Do đó một đống như vậy thường được gọi là đống-max. Nếu mọi phép so sánh bị đảo ngược khiến cho khóa nhỏ nhất luôn nằm ở nút gốc thì đống đó gọi là đống-min. Không có hạn chế nào về số lượng nút con của mỗi nút trong đống nhưng thông thường mỗi nút có không quá hai nút con. Đống là một cách thực hiện kiểu dữ liệu trừu tượng mang tên hàng đợi ưu tiên. Đống có vai trò quan trọng trong nhiều thuật toán cho đồ thị chẳng hạn như thuật toán Dijkstra, hay thuật toán sắp xếp heapsort.

Từ khóa: công nghệ thông tin, cấu trúc đống, dữ liệu tin học, cơ sở thông tin, báo cáo khoa học, chuyên ngành thông tin