Priority queue backed by a sorted linear array. Examples: >>> pq = PriorityQueue([3, 1, 2]) >>> pq.pop() 1 >>> pq.size() 2
| 40 | |
| 41 | |
| 42 | class PriorityQueue: |
| 43 | """Priority queue backed by a sorted linear array. |
| 44 | |
| 45 | Examples: |
| 46 | >>> pq = PriorityQueue([3, 1, 2]) |
| 47 | >>> pq.pop() |
| 48 | 1 |
| 49 | >>> pq.size() |
| 50 | 2 |
| 51 | """ |
| 52 | |
| 53 | def __init__( |
| 54 | self, |
| 55 | items: Iterable[Any] | None = None, |
| 56 | priorities: Iterable[Any] | None = None, |
| 57 | ) -> None: |
| 58 | """Create a priority queue, optionally from items and priorities. |
| 59 | |
| 60 | Args: |
| 61 | items: Initial items to insert. |
| 62 | priorities: Corresponding priorities; defaults to item values. |
| 63 | """ |
| 64 | self.priority_queue_list: list[PriorityQueueNode] = [] |
| 65 | if items is None: |
| 66 | return |
| 67 | if priorities is None: |
| 68 | priorities = itertools.repeat(None) |
| 69 | for item, priority in zip(items, priorities, strict=False): |
| 70 | self.push(item, priority=priority) |
| 71 | |
| 72 | def __repr__(self) -> str: |
| 73 | """Return a string representation of the priority queue. |
| 74 | |
| 75 | Returns: |
| 76 | Formatted string. |
| 77 | """ |
| 78 | return f"PriorityQueue({self.priority_queue_list!r})" |
| 79 | |
| 80 | def size(self) -> int: |
| 81 | """Return the number of elements in the queue. |
| 82 | |
| 83 | Returns: |
| 84 | The queue size. |
| 85 | """ |
| 86 | return len(self.priority_queue_list) |
| 87 | |
| 88 | def push(self, item: Any, priority: Any = None) -> None: |
| 89 | """Insert an item with the given priority. |
| 90 | |
| 91 | Args: |
| 92 | item: The value to insert. |
| 93 | priority: Priority value; defaults to the item itself. |
| 94 | """ |
| 95 | priority = item if priority is None else priority |
| 96 | node = PriorityQueueNode(item, priority) |
| 97 | for index, current in enumerate(self.priority_queue_list): |
| 98 | if current.priority < node.priority: |
| 99 | self.priority_queue_list.insert(index, node) |
no outgoing calls