Bước tới nội dung

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

Bách khoa toàn thư mở Wikipedia
(Đổi hướng từ Heap)

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ể

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồn]

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 [cần dẫn nguồn]
xóa-max * *
chèn *[cần dẫn nguồn]
tăng-khóa * *
hợp ** *

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

Ứng dụng

[sửa | sửa mã nguồn]

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

  1. ^ 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)
  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
  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