Node in a doubly-linked binomial tree, containing: - value - size of left subtree - link to left, right and parent nodes
| 5 | |
| 6 | |
| 7 | class Node: |
| 8 | """ |
| 9 | Node in a doubly-linked binomial tree, containing: |
| 10 | - value |
| 11 | - size of left subtree |
| 12 | - link to left, right and parent nodes |
| 13 | """ |
| 14 | |
| 15 | def __init__(self, val): |
| 16 | self.val = val |
| 17 | # Number of nodes in left subtree |
| 18 | self.left_tree_size = 0 |
| 19 | self.left = None |
| 20 | self.right = None |
| 21 | self.parent = None |
| 22 | |
| 23 | def merge_trees(self, other): |
| 24 | """ |
| 25 | In-place merge of two binomial trees of equal size. |
| 26 | Returns the root of the resulting tree |
| 27 | """ |
| 28 | assert self.left_tree_size == other.left_tree_size, "Unequal Sizes of Blocks" |
| 29 | |
| 30 | if self.val < other.val: |
| 31 | other.left = self.right |
| 32 | other.parent = None |
| 33 | if self.right: |
| 34 | self.right.parent = other |
| 35 | self.right = other |
| 36 | self.left_tree_size = self.left_tree_size * 2 + 1 |
| 37 | return self |
| 38 | else: |
| 39 | self.left = other.right |
| 40 | self.parent = None |
| 41 | if other.right: |
| 42 | other.right.parent = self |
| 43 | other.right = self |
| 44 | other.left_tree_size = other.left_tree_size * 2 + 1 |
| 45 | return other |
| 46 | |
| 47 | |
| 48 | class BinomialHeap: |