Đố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ể

[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.{{Chú thích sách}}: 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–670{{Chú thích}}: Quả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, quyển 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), quyển 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
Chúng tôi bán
Bài viết liên quan
Corpse Bride - tản mạn về phim, cảm xúc của Victor đối với Emily là gì?
Corpse Bride - tản mạn về phim, cảm xúc của Victor đối với Emily là gì?
Victor gặp Emily trong một hoàn cảnh khá trớ trêu. Emily là một cô gái hồng nhan bạc mệnh, vì trót trao nhầm tình yêu cho một kẻ đểu cáng mà ra đi tức tưởi trong bộ váy cưới
Tử Sắc Thủy tổ Ultima (Violet) trong Tensei shitara Slime Datta Ken
Tử Sắc Thủy tổ Ultima (Violet) trong Tensei shitara Slime Datta Ken
Ultima (ウルティマ urutima?), còn được gọi là Violet (原初の紫ヴィオレ viore, lit. "Primordial of Violet"?), là một trong những Primordial gia nhập Tempest sau khi Diablo chiêu mộ cô.
Đôi nét về cuốn sách Nghệ thuật Kaizen tuyệt vời của Toyota
Đôi nét về cuốn sách Nghệ thuật Kaizen tuyệt vời của Toyota
Kaizen được hiểu đơn giản là những thay đổi nhỏ được thực hiện liên tục với mục tiêu cải tiến một sự vật, sự việc theo chiều hướng tốt lên
Mai Sơn Thất Quái và kế hoạch chu toàn của Dương Tiễn.
Mai Sơn Thất Quái và kế hoạch chu toàn của Dương Tiễn.
Tại True Ending của Black Myth: Wukong, chúng ta nhận được cú twist lớn nhất của game, hóa ra Dương Tiễn không phải phản diện mà trái lại, việc tiếp nhận Ý thức của Tôn Ngộ Không