Heap nhị thức là một tập hợp các cây nhị thức. Cây nhị thức Bk là một cây có thứ tự được định nghĩa một cách đệ quy. Cây nhị thức B0 bao gồm một nút duy nhất.
Cây nhị thức Bk bao gồm hai cây nhị thức Bk-1. Điều đó được liên kết với nhau. Gốc của một cái là con ngoài cùng bên trái của gốc của cái kia
Một số đống nhị thức giống như bên dưới -
Một số thuộc tính của cây nhị thức là -
-
Cây nhị thức với B k có 2 k các nút.
-
Chiều cao của cây là k
-
Có chính xác $$ \ left (\ begin {array} {c} k \\ j \ end {array} \ right) $$ nút ở độ sâu thứ i cho tất cả tôi trong phạm vi từ 0 đến k
Khối nhị thức
Một đống nhị thức H là một tập hợp các cây nhị thức. Có một số thuộc tính.
-
Mỗi cây nhị thức trong H được sắp xếp theo thứ tự đống. Vì vậy, khóa của một nút lớn hơn hoặc bằng khóa của nút cha của nó.
-
Có nhiều nhất một cây nhị thức trong H, mà gốc của nó có bậc cho trước.
Ví dụ về đống nhị thức
Nhị thức Heap H này bao gồm các cây nhị thức B0, B2 và B3. Mà có 1, 4 và 8 nút tương ứng. Và trong tổng số n =13 nút. Gốc của cây nhị thức được liên kết bởi một danh sách liên kết theo thứ tự tăng dần