Đống nhị phân

Một đống nhị phân là một cấu trúc dữ liệu đống dựa trên cây nhị phân. Đống nhị phân thường được sử dụng để triển khai hàng đợi ưu tiên^{[1]:162–163}. Đống nhị phân được giới thiệu bởi J. W. J. Williams vào năm 1964, như một cấu trúc dữ liệu dành cho phương pháp sắp xếp heapsort.^[2]

Một đống nhị phân được định nghĩa là một cây nhị phân với hai ràng buộc bổ sung:^[3]

• Đặc tính hình dạng: một đống nhị phân là một cây nhị phân hoàn chỉnh; có nghĩa là, tất cả các cấp của cây, ngoại trừ có thể là cấp cuối cùng (sâu nhất) đều được lấp đầy và nếu cấp cuối cùng của cây không hoàn chỉnh, các nút của cấp đó được lấp đầy từ trái qua phải.
• Đặc tính đống: khóa được lưu trữ trong mỗi nút sẽ lớn hơn hoặc bằng (≥) hoặc nhỏ hơn hoặc bằng (≤) khóa của những nút con, theo một thứ tự toàn phần.

Đống nhị phân mà khóa của nút cha lớn hơn hoặc bằng (≥) khóa của các nút con được gọi là đống nhị phân lớn nhất; những cái mà khóa của nút cha nhỏ hơn hoặc bằng (≤) khóa của các nút con được gọi là đống nhị phân nhỏ nhất. Các thuật toán hiệu quả (thời gian logarithmic) đã được biết để thực hiện hai thao tác cần thiết để triển khai hàng đợi ưu tiên trên một đống nhị phân: chèn một phần tử và loại bỏ phần tử nhỏ nhất hoặc lớn nhất từ một đống nhị phân nhỏ nhất hoặc lớn nhất. Đống nhị phân cũng thường được sử dụng trong thuật toán sắp xếp heapsort, đây là một thuật toán sắp xếp ngay tại chỗ (in-place) bởi vì đống nhị phân có thể được triển khai dưới dạng một cấu trúc dữ liệu ngầm định, lưu trữ khóa trong một mảng và sử dụng vị trí tương đối của chúng trong mảng để đại diện cho quan hệ cha – con.

Như các cấu trúc dữ liệu đống khác, đống nhị phân cho phép thực hiện các thao tác: tìm khóa lớn nhất, xóa khóa lớn nhất, giảm giá trị một khóa, và chèn thêm khóa mới. Ngoài ra, cũng có thể thay đổi cấu trúc dữ liệu đống nhị phân để tìm cả giá trị lớn nhất và nhỏ nhất trong thời gian O(log n)^[4].

Hoạt động của đống

Trong mục này, ta xem xét hoạt động của đống nhị phân cho phép tìm kiếm khóa lớn nhất. Có thể dễ dàng sửa đổi một số chi tiết để tìm khóa nhỏ nhất thay vì lớn nhất.

Chèn

Để chèn thêm một khóa mới, ta thực hiện thuật toán sau:

1. Chèn khóa mới vào tầng cuối cùng của đống
2. So sánh khóa mới với khóa của nút cha, nếu chúng thỏa mãn điều kiện thứ tự của đống, kết thúc.
3. Nếu không, đổi chỗ khóa mới và khóa của nút cha, và trở lại bước trước.

Xóa khóa lớn nhất

Để xóa khóa ở gốc của đống (khóa lớn nhất), ta thực hiện thuật toán sau:

1. Đổi chỗ khóa cần xóa và khóa cuối cùng ở tầng cuối cùng rồi xóa khóa cần xóa khỏi đống. Khởi tạo nút hiện tại là nút gốc.
2. So sánh khóa của nút hiện tại và khóa ở các nút con, nếu chúng thỏa mãn điều kiện thứ tự của đống, kết thúc.
3. Nếu không, đổi chỗ khóa hiện tại và khóa lớn hơn trong các khóa của nút con. Chuyển vị trí nút hiện tại tới nút con vừa được hoán đổi và trở về bước trước.

Lập trình

Đống nhị phân thường được biểu diễn bởi một mảng thay vì một cây nhị phân. Nút cha và nút con của mỗi nút được xác định thông qua một vài phép tính dựa trên chỉ số của mảng, do đó không cần dùng đến con trỏ. Cách biểu diễn này là một ví dụ của cấu trúc dữ liệu ẩn (cấu trúc dữ liệu sử dụng bộ nhớ đúng bằng lượng thông tin cần thiết để lưu trữ dữ liệu, cộng với một lượng nhỏ thông tin phụ).

Giả sử n là số khóa trong đống và i là một chỉ số. Nếu nút gốc có chỉ số 0, và chỉ số các nút là từ 0 đến n-1, thì nút thứ i có

• chỉ số các nút con là 2i+1 và 2i+2
• chỉ số nút cha là ${\displaystyle \lfloor (i-1)/2\rfloor }$

Nếu nút gốc có chỉ số 1, và chỉ số các nút là từ 1 đến n, thì nút thứ i có

• chỉ số các nút con là 2i và 2i+1
• chỉ số nút cha là ${\displaystyle \lfloor i/2\rfloor }$

Xem thêm

• Đống
• Sắp xếp vun đống

Ghi chú

1. Lỗi chú thích: Thẻ <ref> sai; không có nội dung trong thẻ ref có tên clrs
2. Williams, J. W. J. (1964), “Algorithm 232 - Heapsort”, Communications of the ACM, 7 (6): 347–348, doi:10.1145/512274.512284
3. Y Narahari, “Binary Heaps”, Data Structures and Algorithms
4. Atkinson, M.D., J.-R. Sack, N. Santoro, T. Strothotte. “"Min-max heaps and generalized priority queues."” (PDF). Programming techniques and Data structures. Comm. ACM, 29(10): 996–1000. ngày 1 tháng 10 năm 1986. Bản gốc (PDF) lưu trữ ngày 27 tháng 1 năm 2007. Truy cập ngày 17 tháng 6 năm 2011.