Sorts the queue array so that the minimum element is root. Examples: >>> priority_queue_test = PriorityQueue() >>> priority_queue_test.cur_size = 3 >>> priority_queue_test.pos = {'A': 0, 'B': 1, 'C': 2} >>> priority_queue_test.array = [(5, 'A'), (10
(self, idx)
| 42 | return self.cur_size == 0 |
| 43 | |
| 44 | def min_heapify(self, idx): |
| 45 | """ |
| 46 | Sorts the queue array so that the minimum element is root. |
| 47 | |
| 48 | Examples: |
| 49 | >>> priority_queue_test = PriorityQueue() |
| 50 | >>> priority_queue_test.cur_size = 3 |
| 51 | >>> priority_queue_test.pos = {'A': 0, 'B': 1, 'C': 2} |
| 52 | |
| 53 | >>> priority_queue_test.array = [(5, 'A'), (10, 'B'), (15, 'C')] |
| 54 | >>> priority_queue_test.min_heapify(0) |
| 55 | >>> priority_queue_test.array |
| 56 | [(5, 'A'), (10, 'B'), (15, 'C')] |
| 57 | |
| 58 | >>> priority_queue_test.array = [(10, 'A'), (5, 'B'), (15, 'C')] |
| 59 | >>> priority_queue_test.min_heapify(0) |
| 60 | >>> priority_queue_test.array |
| 61 | [(5, 'B'), (10, 'A'), (15, 'C')] |
| 62 | |
| 63 | >>> priority_queue_test.array = [(10, 'A'), (15, 'B'), (5, 'C')] |
| 64 | >>> priority_queue_test.min_heapify(0) |
| 65 | >>> priority_queue_test.array |
| 66 | [(5, 'C'), (15, 'B'), (10, 'A')] |
| 67 | |
| 68 | >>> priority_queue_test.array = [(10, 'A'), (5, 'B')] |
| 69 | >>> priority_queue_test.cur_size = len(priority_queue_test.array) |
| 70 | >>> priority_queue_test.pos = {'A': 0, 'B': 1} |
| 71 | >>> priority_queue_test.min_heapify(0) |
| 72 | >>> priority_queue_test.array |
| 73 | [(5, 'B'), (10, 'A')] |
| 74 | """ |
| 75 | lc = self.left(idx) |
| 76 | rc = self.right(idx) |
| 77 | if lc < self.cur_size and self.array[lc][0] < self.array[idx][0]: |
| 78 | smallest = lc |
| 79 | else: |
| 80 | smallest = idx |
| 81 | if rc < self.cur_size and self.array[rc][0] < self.array[smallest][0]: |
| 82 | smallest = rc |
| 83 | if smallest != idx: |
| 84 | self.swap(idx, smallest) |
| 85 | self.min_heapify(smallest) |
| 86 | |
| 87 | def insert(self, tup): |
| 88 | """ |
no test coverage detected