ArrayHeapPQ¶
-
class
ssds.ArrayHeapPQ(is_max=False)¶ Array-Heap Priority Queue.
Uses an array to store the contents of the heap. Should have \(\mathcal{O}(\log(n))\) adds, removes, and updates.
- Parameters
is_max (bool, default=False) – Selects whether the priority queue should dequeue the item with the maximum priority (instead of the minimum priority).
Examples
>>> from ssds import ArrayHeapPQ >>> pq = ArrayHeapPQ() >>> pq.add('a', 1) >>> pq.add('b', 2) >>> pq.change_priority('b', 0) >>> pq.remove() 'b'
-
add(item, priority: float) → None¶ Adds an item to the priority queue.
- Parameters
item – An item to be inserted into the queue. Does not need to be hashable.
priority (float) – The extrinsic priority of the object.
- Returns
Nothing.
- Return type
None
-
change_priority(item, priority: float) → None¶ Changes the priority of the given item.
- Parameters
item (any) – The item in the priority queue to modify the priority of.
priority (double) – The new priority to set the item to.
- Returns
Nothing.
- Return type
None
-
contains(item) → bool¶ Returns whether the item is in the priority queue or not.
- Parameters
item – An item to test the membership of in the priority queue.
- Returns
Returns True if item is in the priority queue; False otherwise.
- Return type
bool
-
get()¶ Returns the first item in the priority queue.
Which (i.e. minimum or maximum) depends on if the priority queue was initialized as a minimum or maximum priority queue. Does not remove the minimum/maximum item from the queue.
- Parameters
N/A –
- Returns
The foremost item in the priority queue.
- Return type
object
-
remove()¶ Removes and returns the first item in the priority queue.
Which (i.e. minimum or maximum) depends on if the priority queue was initialized as a minimum or maximum priority queue.
- Parameters
N/A –
- Returns
The foremost item in the priority queue.
- Return type
object
-
size() → int¶ Returns the number of items in the priority queue.
- Parameters
N/A –
- Returns
The number of items in the priority queue.
- Return type
int