>>> r = Node("R", -1) >>> b = Node("B", 6) >>> a = Node("A", 3) >>> x = Node("X", 1) >>> e = Node("E", 4) >>> print(b) Node(B, 6) >>> myMinHeap = MinHeap([r, b, a, x, e]) >>> myMinHeap.decrease_key(b, -17) >>> print(b) Node(B, -17) >>> myMinHeap["B"]
| 15 | |
| 16 | |
| 17 | class MinHeap: |
| 18 | """ |
| 19 | >>> r = Node("R", -1) |
| 20 | >>> b = Node("B", 6) |
| 21 | >>> a = Node("A", 3) |
| 22 | >>> x = Node("X", 1) |
| 23 | >>> e = Node("E", 4) |
| 24 | >>> print(b) |
| 25 | Node(B, 6) |
| 26 | >>> myMinHeap = MinHeap([r, b, a, x, e]) |
| 27 | >>> myMinHeap.decrease_key(b, -17) |
| 28 | >>> print(b) |
| 29 | Node(B, -17) |
| 30 | >>> myMinHeap["B"] |
| 31 | -17 |
| 32 | """ |
| 33 | |
| 34 | def __init__(self, array): |
| 35 | self.idx_of_element = {} |
| 36 | self.heap_dict = {} |
| 37 | self.heap = self.build_heap(array) |
| 38 | |
| 39 | def __getitem__(self, key): |
| 40 | return self.get_value(key) |
| 41 | |
| 42 | def get_parent_idx(self, idx): |
| 43 | return (idx - 1) // 2 |
| 44 | |
| 45 | def get_left_child_idx(self, idx): |
| 46 | return idx * 2 + 1 |
| 47 | |
| 48 | def get_right_child_idx(self, idx): |
| 49 | return idx * 2 + 2 |
| 50 | |
| 51 | def get_value(self, key): |
| 52 | return self.heap_dict[key] |
| 53 | |
| 54 | def build_heap(self, array): |
| 55 | last_idx = len(array) - 1 |
| 56 | start_from = self.get_parent_idx(last_idx) |
| 57 | |
| 58 | for idx, i in enumerate(array): |
| 59 | self.idx_of_element[i] = idx |
| 60 | self.heap_dict[i.name] = i.val |
| 61 | |
| 62 | for i in range(start_from, -1, -1): |
| 63 | self.sift_down(i, array) |
| 64 | return array |
| 65 | |
| 66 | # this is min-heapify method |
| 67 | def sift_down(self, idx, array): |
| 68 | while True: |
| 69 | left = self.get_left_child_idx(idx) |
| 70 | right = self.get_right_child_idx(idx) |
| 71 | |
| 72 | smallest = idx |
| 73 | if left < len(array) and array[left] < array[idx]: |
| 74 | smallest = left |