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

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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.

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 đống-max (tìm khóa nhỏ nhất trong đống-min).
  • xóa-max (xóa-min): xóa nút gốc của đống-max (đống-min)
  • tăng-khóa (giảm-khóa): thay đổi giá trị một khóa trong đống-max (đống-min)
  • 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 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[sửa | sửa mã nguồn]

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

Xem thêm[sửa | sửa mã nguồn]

Ghi chú[sửa | sửa mã nguồn]

  1. ^ a ă â b Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2009). Introduction to algorithms. MIT Press / McGraw-Hill. 
  2. ^ Bernhard Haeupler,Siddhartha Sen,Robert Endre Tarjan (2009), “Rank-Pairing Heaps”, ESA, tr. 659–670 
  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 104 (2), Academic Press, tr. 197–214, doi:10.1006/inco.1993.1030