Đống(Heap) là một cây dữ liệu cấu trúc đáp ứng điều kiện; nếu B là con của A thì key(A)  >= key(B). Nghĩa là một phần tử lớn nhất luôn là nút gốc đối với max-heap, ngược lại phần tử nhỏ nhất luôn là nút gốc với min-heap. Số lượng nút con tối đa có thể phụ thuộc vào loại của heap, nhưng rất nhiều loại đó là hai. Heap là một trong những hiệu quả tối đa thực hiện của một kiểu dữ liệu trừu tượng được gọi là hàng đợi ưu tiên. Heap rất quan trọng trong một số thuật toán đồ thị như thuật toán Dịkstra, và thuật toán sắp xếp heapsort.

Cấu trúc dữ liệu heap không nên nhẫm lẫn với đống thường được gọi là bộ nhớ tự động cấp phát.

Heap thường thực hiện trong mảng và không đòi hỏi con trỏ giữa các yếu tố

Các hoạt động thường được thực hiện với một đống :

·  tạo-heap: tạo ra một đống rỗng

·  tìm max hoặc tìm-min: tìm thấy các khóa max của một max-heap hoặc một khóa tối thiểu của một min-heap.

·  xóa max hoặc xóa-min: loại bỏ các nút gốc của một max-heap hoặc min-heap.

·  tăng-key hoặc giảm key: cập nhật một khóa trong một max-heap hoặc       min-heap.

·  chèn: thêm một khóa mới vào heap

·  hợp nhất: kết nối hai đống để tạo thành một đống hợp lệ mới có chứa tất cả các yếu tố của cả hai.

Đống  nhị thức cho phép những hiệu quả không thể có trong đống nhị phân.  Chi phí tối thiểu phải trả là những thao tác tối thiểu mà bây giờ yêu cầu là O(log n).

1, Cây nhị thức:

Một cây nhị thức Bk  là một cây có thứ tự quy định đệ quy.

-B0 bao gồm một nút duy nhất.

-Đối với k >= 1, Bk là một cặpghép của cây Bk-1 , nơi mà gốc của Bk-1  trở thành cây con tận cùng bên trái của cây khác.

Hình 1: một số cây nhị thức

b, Tính chất của cây nhị thức:

Bổ đề A: Đối với tất cả các số nguyên k >= 0, các tính chất:

·        Bk có 2k nút.

·        Bk có chiều cao là k.

·        Đối với i=0,..,k, Bk có chính xác (k/i) nút ở độ sâu i.

·        Gốc của Bk có bậc k và các nút khác trên Bk có bậc nhỏ hơn k.

·        Nếu k>=1, nút con của gốc của Bk là B­k-1, Bk-2,….,B0  từ trái sang phải.

Hệ lụy B: Bậc lớn nhất của một cây nhị thức n nút là lg(n).

2, Đống nhị thức:

Một đống nhị thức là một bộ của cây nhị thức thỏa mãn các tính chất sau:

·        Không có hai cây nhị thức trong bộ có cùng kích thước.

·        Mỗi nút trên mỗi cây có một khóa.

·        Mỗi cây nhị thức trong bộ là đống sắp xếp theo  nghĩa là mỗi nút không phải là gốc là khóa đúng nhỏ hơn khóa của nút cha của nó.

Đối với tính chất đầu tiên, chúng ta có những điều sau:   Đối với tất cả n>=1 và k>=0, Bk xuất hiện trên một đống nhị phân n nút nếu và chỉ nếu có (k+1) bít của biểu diễn nhị phân của n là 1.

Điều này có nghĩa là số cây trong một đống là O(log n)

3. Kiến trúc của một đống nhị thức:

Giữ tại mỗi nút theo các mảnh thông tin sau:

          -Trường key cho khóa

          -Trường degree cho số nút con

          -Con trỏ child  chỉ vào cây con tận cùng bên trái.

          -Con trỏ sibling chỉ vào họ bên phải

          -Và con trỏ p chỉ vào nút cha

Các gốc của cây được kết nối, vì thế các kích thước của chúng giảm đi. Ngoài ra, với một đống H, head[H] chỉ ra nút đầu của dãy.

4. Các hành động với đống nhị thức:

Bởi vì hoạt động không đòi hỏi phải truy cập ngẫu nhiên các nút gốc của các cây nhị thức, các gốc của những cây nhị thức có thể được lưu trữ trong một danh sách liên kết , sắp xếp theo thứ tự tăng dần của cây.

          -Tạo đống mới

          -Tìm khóa nhỏ nhất

          -Kết hợp hai đống nhị thức

-Chèn vào một nút

-Loại bỏ gốc của một cây

-Giảm khóa

-Loại bỏ một nút

a, Tạo đống mới:

          Để tạo đống H viết:  head[H]=nil

b, Tìm khóa nhỏ nhất

Để làm được điều này, chúng tatìm khóa nhỏ nhất trong số những khóa được lưu trữ ở các gốc kết nối vớihead của H.

Độ phức tạp là O(log n) bởi vì có O(log n), trên mỗi cây, khóa nhỏ nhất là nằm ở gốc, và các gốc liên kết với nhau.

c, Kết hợp hai đống nhị thức

Chúng ta muốn để hợp nhất hai đống nhị thứcH1 và H2 có kíchthước n1 và n2tương ứng.

Khi kết hợp hai heap, so sánh hai gốc với nhau để xem heap nào trở thành con của heap nào tùy theo loại heap, nút gốc còn lại là gốc của heap mới.

function mergeTree(p, q)

    if p.root.key <= q.root.key

        return p.addSubTree(q)

    else

        return q.addSubTree(p)

function merge(p, q)

    while not( p.end() and q.end() )

        tree = mergeTree(p.currentTree(), q.currentTree())

        if not heap.currentTree().empty()

            tree = mergeTree(tree, heap.currentTree())

            heap.addTree(tree)

        else

            heap.addTree(tree)

        heap.next() p.next() q.next()

d,  Chèn vào một nút:

Giả sử chúng ta muốn chèn một nút x vào mộtđống nhị thứcH.

Chúng ta tạo ra một đống nútđơnH’bao gồmx và kết nối H và H’

e, Loại bỏ gốc của một cây T:

Chúng ta loại bỏ T từ H và tạo ra một đống H’ chỉ bao gồm các nút con của T. Sau đó,chúng ta kết nối H và H’.

f, Giảm khóa

Chúng ta giảm khóa và sau đó tiếp tục thay đổi các khóa lên trên cho đến khi việc vi phạm các thuộc tính của đống được giải quyết.

g, Loại bỏ một nút

Chúng ta giảm khóa đến -∞ để di chuyển khóa đến vị trí gốc. Sau đó chung ta sử dụng loại bỏ gốc.