Đống nhị phân

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

Một đống nhị phân (tiếng Anh: binary heap) là một cấu trúc dữ liệu đống sử dụng cây nhị phân. Đống nhị phân là một cây nhị phân với hai hạn chế bổ sung:

  • Cây nhị phân là hoàn chỉnh: tất cả các tầng của cây ngoại trừ tầng cuối cùng (sâu nhất) đều đầy đủ, và nếu tầng cuối cùng không đầy đủ thì các nút ở tầng đó phải lấp đầy các vị trí theo thứ tự từ trái sang phải.
  • Khóa của mỗi nút lớn hơn hoặc bằng khóa của các nút con của nó.

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ó 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)[1].

Hoạt động của đống[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồ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[sửa | sửa mã nguồn]

Để 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[sửa | sửa mã nguồn]

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

  • chỉ số các nút con là 2i+12i+2
  • chỉ số nút cha là \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

  • chỉ số các nút con là 2i2i+1
  • chỉ số nút cha là \lfloor i/2\rfloor

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

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

  1. ^ Atkinson, M.D., J.-R. Sack, N. Santoro, T. Strothotte. “"Min-max heaps and generalized priority queues."”. Programming techniques and Data structures. Comm. ACM, 29(10): 996–1000. October 1, 1986.