In-place merge of two binomial heaps. Both of them become the resulting merged heap
(self, other)
| 129 | self.min_node = min_node |
| 130 | |
| 131 | def merge_heaps(self, other): |
| 132 | """ |
| 133 | In-place merge of two binomial heaps. |
| 134 | Both of them become the resulting merged heap |
| 135 | """ |
| 136 | |
| 137 | # Empty heaps corner cases |
| 138 | if other.size == 0: |
| 139 | return None |
| 140 | if self.size == 0: |
| 141 | self.size = other.size |
| 142 | self.bottom_root = other.bottom_root |
| 143 | self.min_node = other.min_node |
| 144 | return None |
| 145 | # Update size |
| 146 | self.size = self.size + other.size |
| 147 | |
| 148 | # Update min.node |
| 149 | if self.min_node.val > other.min_node.val: |
| 150 | self.min_node = other.min_node |
| 151 | # Merge |
| 152 | |
| 153 | # Order roots by left_subtree_size |
| 154 | combined_roots_list = [] |
| 155 | i, j = self.bottom_root, other.bottom_root |
| 156 | while i or j: |
| 157 | if i and ((not j) or i.left_tree_size < j.left_tree_size): |
| 158 | combined_roots_list.append((i, True)) |
| 159 | i = i.parent |
| 160 | else: |
| 161 | combined_roots_list.append((j, False)) |
| 162 | j = j.parent |
| 163 | # Insert links between them |
| 164 | for i in range(len(combined_roots_list) - 1): |
| 165 | if combined_roots_list[i][1] != combined_roots_list[i + 1][1]: |
| 166 | combined_roots_list[i][0].parent = combined_roots_list[i + 1][0] |
| 167 | combined_roots_list[i + 1][0].left = combined_roots_list[i][0] |
| 168 | # Consecutively merge roots with same left_tree_size |
| 169 | i = combined_roots_list[0][0] |
| 170 | while i.parent: |
| 171 | if ( |
| 172 | (i.left_tree_size == i.parent.left_tree_size) and (not i.parent.parent) |
| 173 | ) or ( |
| 174 | i.left_tree_size == i.parent.left_tree_size |
| 175 | and i.left_tree_size != i.parent.parent.left_tree_size |
| 176 | ): |
| 177 | # Neighbouring Nodes |
| 178 | previous_node = i.left |
| 179 | next_node = i.parent.parent |
| 180 | |
| 181 | # Merging trees |
| 182 | i = i.merge_trees(i.parent) |
| 183 | |
| 184 | # Updating links |
| 185 | i.left = previous_node |
| 186 | i.parent = next_node |
| 187 | if previous_node: |
| 188 | previous_node.parent = i |
no test coverage detected