Removes and returns the min element at top of priority queue. Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.array = [(10, 'A'), (15, 'B')] >>> priority_queue_test.cur_size = len(priority_queue_test.array) >>> priority_qu
(self)
| 106 | self.decrease_key((sys.maxsize, tup[1]), tup[0]) |
| 107 | |
| 108 | def extract_min(self): |
| 109 | """ |
| 110 | Removes and returns the min element at top of priority queue. |
| 111 | |
| 112 | Examples: |
| 113 | >>> priority_queue_test = PriorityQueue() |
| 114 | >>> priority_queue_test.array = [(10, 'A'), (15, 'B')] |
| 115 | >>> priority_queue_test.cur_size = len(priority_queue_test.array) |
| 116 | >>> priority_queue_test.pos = {'A': 0, 'B': 1} |
| 117 | >>> priority_queue_test.insert((5, 'C')) |
| 118 | >>> priority_queue_test.extract_min() |
| 119 | 'C' |
| 120 | >>> priority_queue_test.array[0] |
| 121 | (10, 'A') |
| 122 | """ |
| 123 | min_node = self.array[0][1] |
| 124 | self.array[0] = self.array[self.cur_size - 1] |
| 125 | self.cur_size -= 1 |
| 126 | self.min_heapify(0) |
| 127 | del self.pos[min_node] |
| 128 | return min_node |
| 129 | |
| 130 | def left(self, i): |
| 131 | """ |