A library for Priory-Queues containing Indexed-Priority-Queue and Simple Priority-Queue
A library for Priority-Queues containing Indexed-Priority-Queue and Simple Priority-Queue.
clone the this reporitory using,
or, install using pip,
pip install pyqueues
Works with Python 3.x and PyPy.
Both, the Indexed priority queue and the queue has been implemented as a min binary heap to use it as a max heap or to uea it with custome key pass the values as a tuple in the heaps eg. (key, value). The time complexities are,
peek highest priority element: O(1)
pop highest priority element: O(log n)
push new element: O(log n)
additionally for Indexed Priority Queue,
lookup of any item by key: O(1)
remove element by key: O(log n)
update element by key: O(log n)
from pyqueues.indexedPriorityQueue import IndexedPriorityQueue from pyqueues.heap import heapify, heapPop, heapPush
to heapify a list (does not changes the original list, but heapifies internally),
arr = [10, 20, 15, 12, 40, 25, 18, 40] pq = IndexedPriorityQueue(arr) pq.heapify()
to push items into the priority queue,
to update a item using key (we an saperatly keep track of the key of the values using a dict by mapping values to the arrSize arrtibute of the priority queue)
pq.update(pq.arrSize-1, 100) # updates -1 to 100 pq.update(pq.arrSize-2, -1) # updates 2 to -1
"similarly use pq.decreaseKey() and pq.increaseKey() methods (works in half of, the time required for update method), when we know that we are increseing or decresing the values while updating."
to remove a values from priority queue,
pq.remove(pq.arrSize-1) # removes 100
to pop highest priority element,
pq.pop() # pops -1
Copyright (c) 2020 abecus
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
|Filename, size||File type||Python version||Upload date||Hashes|
|Filename, size pyqueues-1.2.tar.gz (5.3 kB)||File type Source||Python version None||Upload date||Hashes View|