Đống (cấu trúc dữ liệu)

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à max-heap. 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à min-heap. 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.

Không nên nhầm lẫn cấu trúc dữ liệu đống với đống thường được dùng cho bộ nhớ cấp phát động. Thuật ngữ này ban đầu chỉ được dùng cho cấu trúc dữ liệu, nhưng sau này cũng được dùng để chỉ các vùng bộ nhớ cấp phát động^[1].

Các thao tác thường gặp trên đống là:

tìm-max (tìm-min): tìm khóa lớn nhất trong max-heap (tìm khóa nhỏ nhất trong đống-min).
xóa-max (xóa-min): xóa nút gốc của max-heap (min-heap)
tăng-khóa (giảm-khóa): thay đổi giá trị một khóa trong max-heap (min-heap)
chèn: chèn thêm một khóa mới vào đống
hợp: hợp hai đống lại thành một đống mới chứa tất cả các khóa của cả hai

Các biến thể

So sánh các biến thể

Bảng sau đây thống kê độ phức tạp tính toán của các thao tác trên đống. Tất cả các mục đều là thời gian xấu nhất ngoại trừ các mục được đánh dấu sao là thời gian trả dần. Tên hàm được đặt theo đống-max.

Thao tác	Nhị phân^[1]	Nhị thức^[1]	Fibonacci^[1]	Ghép^[4]
tìm-max	$O(1)$	$O(1)$	$O(1)$	$O(1)$ ^{[cần dẫn nguồn]}
xóa-max	$O(\log n)$	$O(\log n)$	$O(\log n)$ *	$O(\log n)$ *
chèn	$O(\log n)$	$O(\log n)$	$O(1)$	$O(1)$ *^{[cần dẫn nguồn]}
tăng-khóa	$O(\log n)$	$O(\log n)$	$O(1)$ *	$O(\log n)$ *
hợp	$O(n)$	$O(\log n)$ **	$O(1)$	$O(1)$ *

(*)Thời gian trả dần
(**)n là kích thước của đống lớn hơn

Ứng dụng

Cấu trúc dữ liệu đống có rất nhiều ứng dụng.

Heapsort: Một trong những phương pháp sắp xếp tại chỗ tốt nhất
Thuật toán lựa chọn: có thể sử dụng đống để tìm phần tử lớn nhất, nhỏ nhất, trung vị, phần tử lớn thứ k, trong thời gian tuyến tính.^[5]
Thuật toán cho đồ thị: nhiều thuật toán cho đồ thị sử dụng cấu trúc dữ liệu đống chẳng hạn như thuật toán Dijkstra, hay thuật toán Prim.

Xem thêm

Ghi chú

^ ^a ^b ^c ^d Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009). Introduction to algorithms. MIT Press / McGraw-Hill.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
^ Bernhard Haeupler,Siddhartha Sen,Robert Endre Tarjan (2009), “Rank-Pairing Heaps”, ESA, tr. 659–670Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
^ Bernard Chazelle (2000), “The soft heap: an approximate priority queue with optimal error rate”, J. ACM, 47 (6): 1012–1027
^ Iacono, John (2000), “Improved upper bounds for pairing heaps”, Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, 1851, Springer-Verlag, tr. 63–77, doi:10.1007/3-540-44985-X_5
^ Frederickson, Greg N. (1993), “An Optimal Algorithm for Selection in a Min-Heap”, Information and Computation (PDF), 104, Academic Press, tr. 197–214, doi:10.1006/inco.1993.1030, Bản gốc (PDF) lưu trữ ngày 3 tháng 12 năm 2012, truy cập ngày 20 tháng 6 năm 2011

[CLRS-1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009). Introduction to algorithms. MIT Press / McGraw-Hill.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)

[2] Bernhard Haeupler,Siddhartha Sen,Robert Endre Tarjan (2009), “Rank-Pairing Heaps”, ESA, tr. 659–670Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)

[3] Bernard Chazelle (2000), “The soft heap: an approximate priority queue with optimal error rate”, J. ACM, 47 (6): 1012–1027

[Iacono-4] Iacono, John (2000), “Improved upper bounds for pairing heaps”, Proc. 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, 1851, Springer-Verlag, tr. 63–77, doi:10.1007/3-540-44985-X_5

[5] Frederickson, Greg N. (1993), “An Optimal Algorithm for Selection in a Min-Heap”, Information and Computation (PDF), 104, Academic Press, tr. 197–214, doi:10.1006/inco.1993.1030, Bản gốc (PDF) lưu trữ ngày 3 tháng 12 năm 2012, truy cập ngày 20 tháng 6 năm 2011

[1]

[2]

[3]

[4]

[5]