Popular recipes tagged "priority_queue"http://code.activestate.com/recipes/tags/priority_queue/popular/2013-12-08T21:12:55-08:00ActiveState Code RecipesPriority Queue (with deletion) (Python)
2013-12-08T21:12:55-08:00elazarhttp://code.activestate.com/recipes/users/4187847/http://code.activestate.com/recipes/578780-priority-queue-with-deletion/
<p style="color: grey">
Python
recipe 578780
by <a href="/recipes/users/4187847/">elazar</a>
(<a href="/recipes/tags/artificial_intelligence/">artificial_intelligence</a>, <a href="/recipes/tags/heap/">heap</a>, <a href="/recipes/tags/heapq/">heapq</a>, <a href="/recipes/tags/priority_queue/">priority_queue</a>, <a href="/recipes/tags/queue/">queue</a>).
Revision 5.
</p>
<p>Based on the interface defined in aima-python
<a href="http://aima-python.googlecode.com/svn/trunk/utils.py" rel="nofollow">http://aima-python.googlecode.com/svn/trunk/utils.py</a></p>
<p>Yields better performance.</p>
Priority queue dictionary (Python)
2013-08-25T00:23:12-07:00Nezar Abdennurhttp://code.activestate.com/recipes/users/4187557/http://code.activestate.com/recipes/578643-priority-queue-dictionary/
<p style="color: grey">
Python
recipe 578643
by <a href="/recipes/users/4187557/">Nezar Abdennur</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>, <a href="/recipes/tags/dictionary/">dictionary</a>, <a href="/recipes/tags/heap/">heap</a>, <a href="/recipes/tags/heapq/">heapq</a>, <a href="/recipes/tags/pqdict/">pqdict</a>, <a href="/recipes/tags/priority_queue/">priority_queue</a>).
Revision 4.
</p>
<p>An indexed priority queue implemented in pure python as a dict-like class. It is a stripped-down version of <a href="https://pypi.python.org/pypi/pqdict/">pqdict</a>. A Priority Queue Dictionary maps dictionary keys (dkeys) to updatable priority keys (pkeys).</p>
<p>The priority queue is implemented as a binary heap, which supports: </p>
<ul>
<li><p>O(1) access to the top priority element </p></li>
<li><p>O(log n) removal of the top priority element </p></li>
<li><p>O(log n) insertion of a new element</p></li>
</ul>
<p>In addition, an internal dictionary or "index" maps dictionary keys to the position of their entry in the heap. This index is maintained as the heap is manipulated. As a result, a PQ-dict also supports: </p>
<ul>
<li><p>O(1) lookup of an arbitrary element's priority key </p></li>
<li><p>O(log n) removal of an arbitrary element </p></li>
<li><p>O(log n) updating of an arbitrary element's priority key</p></li>
</ul>
<p>A data structure like this can be used to drive simulations, schedulers, certain greedy algorithms, merging streams of sorted data, and other applications where priorities may need to be changed frequently.</p>