| 3 | |
| 4 | |
| 5 | class Heap: |
| 6 | def __init__(self): |
| 7 | self.node_position = [] |
| 8 | |
| 9 | def get_position(self, vertex): |
| 10 | return self.node_position[vertex] |
| 11 | |
| 12 | def set_position(self, vertex, pos): |
| 13 | self.node_position[vertex] = pos |
| 14 | |
| 15 | def top_to_bottom(self, heap, start, size, positions): |
| 16 | if start > size // 2 - 1: |
| 17 | return |
| 18 | else: |
| 19 | if 2 * start + 2 >= size: # noqa: SIM114 |
| 20 | smallest_child = 2 * start + 1 |
| 21 | elif heap[2 * start + 1] < heap[2 * start + 2]: |
| 22 | smallest_child = 2 * start + 1 |
| 23 | else: |
| 24 | smallest_child = 2 * start + 2 |
| 25 | if heap[smallest_child] < heap[start]: |
| 26 | temp, temp1 = heap[smallest_child], positions[smallest_child] |
| 27 | heap[smallest_child], positions[smallest_child] = ( |
| 28 | heap[start], |
| 29 | positions[start], |
| 30 | ) |
| 31 | heap[start], positions[start] = temp, temp1 |
| 32 | |
| 33 | temp = self.get_position(positions[smallest_child]) |
| 34 | self.set_position( |
| 35 | positions[smallest_child], self.get_position(positions[start]) |
| 36 | ) |
| 37 | self.set_position(positions[start], temp) |
| 38 | |
| 39 | self.top_to_bottom(heap, smallest_child, size, positions) |
| 40 | |
| 41 | # Update function if value of any node in min-heap decreases |
| 42 | def bottom_to_top(self, val, index, heap, position): |
| 43 | temp = position[index] |
| 44 | |
| 45 | while index != 0: |
| 46 | parent = int((index - 2) / 2) if index % 2 == 0 else int((index - 1) / 2) |
| 47 | |
| 48 | if val < heap[parent]: |
| 49 | heap[index] = heap[parent] |
| 50 | position[index] = position[parent] |
| 51 | self.set_position(position[parent], index) |
| 52 | else: |
| 53 | heap[index] = val |
| 54 | position[index] = temp |
| 55 | self.set_position(temp, index) |
| 56 | break |
| 57 | index = parent |
| 58 | else: |
| 59 | heap[0] = val |
| 60 | position[0] = temp |
| 61 | self.set_position(temp, 0) |
| 62 | |