Remove an element from the queue.
(self, elt)
| 113 | self._siftdown(pos) |
| 114 | |
| 115 | def remove(self, elt): |
| 116 | """Remove an element from the queue.""" |
| 117 | # Find and remove element |
| 118 | try: |
| 119 | pos = self.d[elt] |
| 120 | del self.d[elt] |
| 121 | except KeyError: |
| 122 | # Not in queue |
| 123 | raise |
| 124 | # If elt is last item, remove and return |
| 125 | if pos == len(self.h) - 1: |
| 126 | self.h.pop() |
| 127 | return |
| 128 | # Replace elt with last element |
| 129 | last = self.h.pop() |
| 130 | self.h[pos] = last |
| 131 | self.d[last] = pos |
| 132 | # Restore invariant by sifting up, then down |
| 133 | pos = self._siftup(pos) |
| 134 | self._siftdown(pos) |
| 135 | |
| 136 | def _siftup(self, pos): |
| 137 | """Move element at pos down to a leaf by repeatedly moving the smaller |