Remove an element from the queue.
(self, elt)
| 217 | self._siftup(pos) |
| 218 | |
| 219 | def remove(self, elt): |
| 220 | """Remove an element from the queue.""" |
| 221 | # Find and remove element |
| 222 | try: |
| 223 | pos = self.position[elt] |
| 224 | del self.position[elt] |
| 225 | except KeyError: |
| 226 | # Not in queue |
| 227 | raise |
| 228 | # If elt is last item, remove and return |
| 229 | if pos == len(self.heap) - 1: |
| 230 | self.heap.pop() |
| 231 | return |
| 232 | # Replace elt with last element |
| 233 | last = self.heap.pop() |
| 234 | self.heap[pos] = last |
| 235 | self.position[last] = pos |
| 236 | # Restore invariant by sifting up |
| 237 | self._siftup(pos) |
| 238 | |
| 239 | def _siftup(self, pos): |
| 240 | """Move smaller child up until hitting a leaf. |