Start at the end of the tree (last enqueued item). Compare the rear item to its parent, swap if the parent is larger than the child (min-heap property). Repeat until the min-heap property is met. Best Case: O(1), item is inserted at correct position, no s
(self)
| 44 | self.heapify_up() |
| 45 | |
| 46 | def heapify_up(self): |
| 47 | """ |
| 48 | Start at the end of the tree (last enqueued item). |
| 49 | |
| 50 | Compare the rear item to its parent, swap if |
| 51 | the parent is larger than the child (min-heap property). |
| 52 | Repeat until the min-heap property is met. |
| 53 | |
| 54 | Best Case: O(1), item is inserted at correct position, no swaps needed |
| 55 | Worst Case: O(log n), item needs to be swapped throughout all levels of tree |
| 56 | """ |
| 57 | child = self.rear |
| 58 | parent = self.parent_idx(child) |
| 59 | while self.queue[child] < self.queue[self.parent_idx(child)]: |
| 60 | # Swap (sift up) and update child:parent relation |
| 61 | self.queue[child], self.queue[parent] = self.queue[parent], self.queue[child] |
| 62 | child = parent |
| 63 | parent = self.parent_idx(child) |
| 64 | |
| 65 | def pop(self): |
| 66 | """ |