insert a value in the heap
(self, val)
| 204 | return self |
| 205 | |
| 206 | def insert(self, val): |
| 207 | """ |
| 208 | insert a value in the heap |
| 209 | """ |
| 210 | if self.size == 0: |
| 211 | self.bottom_root = Node(val) |
| 212 | self.size = 1 |
| 213 | self.min_node = self.bottom_root |
| 214 | else: |
| 215 | # Create new node |
| 216 | new_node = Node(val) |
| 217 | |
| 218 | # Update size |
| 219 | self.size += 1 |
| 220 | |
| 221 | # update min_node |
| 222 | if val < self.min_node.val: |
| 223 | self.min_node = new_node |
| 224 | # Put new_node as a bottom_root in heap |
| 225 | self.bottom_root.left = new_node |
| 226 | new_node.parent = self.bottom_root |
| 227 | self.bottom_root = new_node |
| 228 | |
| 229 | # Consecutively merge roots with same left_tree_size |
| 230 | while ( |
| 231 | self.bottom_root.parent |
| 232 | and self.bottom_root.left_tree_size |
| 233 | == self.bottom_root.parent.left_tree_size |
| 234 | ): |
| 235 | # Next node |
| 236 | next_node = self.bottom_root.parent.parent |
| 237 | |
| 238 | # Merge |
| 239 | self.bottom_root = self.bottom_root.merge_trees(self.bottom_root.parent) |
| 240 | |
| 241 | # Update Links |
| 242 | self.bottom_root.parent = next_node |
| 243 | self.bottom_root.left = None |
| 244 | if next_node: |
| 245 | next_node.left = self.bottom_root |
| 246 | |
| 247 | def peek(self): |
| 248 | """ |
nothing calls this directly
no test coverage detected