Minimum Priority Queue Class Functions: is_empty: function to check if the priority queue is empty push: function to add an element with given priority to the queue extract_min: function to remove and return the element with lowest weight (highest priority)
| 48 | |
| 49 | |
| 50 | class MinPriorityQueue[T]: |
| 51 | """ |
| 52 | Minimum Priority Queue Class |
| 53 | |
| 54 | Functions: |
| 55 | is_empty: function to check if the priority queue is empty |
| 56 | push: function to add an element with given priority to the queue |
| 57 | extract_min: function to remove and return the element with lowest weight (highest |
| 58 | priority) |
| 59 | update_key: function to update the weight of the given key |
| 60 | _bubble_up: helper function to place a node at the proper position (upward |
| 61 | movement) |
| 62 | _bubble_down: helper function to place a node at the proper position (downward |
| 63 | movement) |
| 64 | _swap_nodes: helper function to swap the nodes at the given positions |
| 65 | |
| 66 | >>> queue = MinPriorityQueue() |
| 67 | |
| 68 | >>> queue.push(1, 1000) |
| 69 | >>> queue.push(2, 100) |
| 70 | >>> queue.push(3, 4000) |
| 71 | >>> queue.push(4, 3000) |
| 72 | |
| 73 | >>> queue.extract_min() |
| 74 | 2 |
| 75 | |
| 76 | >>> queue.update_key(4, 50) |
| 77 | |
| 78 | >>> queue.extract_min() |
| 79 | 4 |
| 80 | >>> queue.extract_min() |
| 81 | 1 |
| 82 | >>> queue.extract_min() |
| 83 | 3 |
| 84 | """ |
| 85 | |
| 86 | def __init__(self) -> None: |
| 87 | self.heap: list[tuple[T, int]] = [] |
| 88 | self.position_map: dict[T, int] = {} |
| 89 | self.elements: int = 0 |
| 90 | |
| 91 | def __len__(self) -> int: |
| 92 | return self.elements |
| 93 | |
| 94 | def __repr__(self) -> str: |
| 95 | return str(self.heap) |
| 96 | |
| 97 | def is_empty(self) -> bool: |
| 98 | # Check if the priority queue is empty |
| 99 | return self.elements == 0 |
| 100 | |
| 101 | def push(self, elem: T, weight: int) -> None: |
| 102 | # Add an element with given priority to the queue |
| 103 | self.heap.append((elem, weight)) |
| 104 | self.position_map[elem] = self.elements |
| 105 | self.elements += 1 |
| 106 | self._bubble_up(elem) |
| 107 |