Remove and return the smallest element in the queue.
(self)
| 83 | return True |
| 84 | |
| 85 | def pop(self): |
| 86 | """Remove and return the smallest element in the queue.""" |
| 87 | # Remove smallest element |
| 88 | elt = self.h[0] |
| 89 | del self.d[elt] |
| 90 | # If elt is last item, remove and return |
| 91 | if len(self.h) == 1: |
| 92 | self.h.pop() |
| 93 | return elt |
| 94 | # Replace root with last element |
| 95 | last = self.h.pop() |
| 96 | self.h[0] = last |
| 97 | self.d[last] = 0 |
| 98 | # Restore invariant by sifting up, then down |
| 99 | pos = self._siftup(0) |
| 100 | self._siftdown(pos) |
| 101 | # Return smallest element |
| 102 | return elt |
| 103 | |
| 104 | def update(self, elt, new): |
| 105 | """Replace an element in the queue with a new one.""" |
no test coverage detected