http://code.activestate.com/recipes/tags/heap-python/2015-09-17T12:41:15-07:00ActiveState Code Recipes2013-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>

2015-09-17T12:41:15-07:00yotahttp://code.activestate.com/recipes/users/4184815/http://code.activestate.com/recipes/578694-heap-class/

<p style="color: grey"> Python recipe 578694 by <a href="/recipes/users/4184815/">yota</a> (<a href="/recipes/tags/heap/">heap</a>). Revision 2. </p> <p><em>heapq</em> is a nice python module, but the interface is not so clean. I found a one-liner on this <a href="http://metapython.blogspot.de/2010/10/creating-heap-class-in-one-python-line.html">blog</a>, it's as short as possible, but not really pythonic either :) Here is my contribution to a most readable heap class.</p>

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>

2011-05-12T01:39:18-07:00huang chongdihttp://code.activestate.com/recipes/users/4177954/http://code.activestate.com/recipes/577688-heap-sort/

<p style="color: grey"> Python recipe 577688 by <a href="/recipes/users/4177954/">huang chongdi</a> (<a href="/recipes/tags/heap/">heap</a>, <a href="/recipes/tags/sort/">sort</a>). </p> <p>a python version of heap sort</p>