http://code.activestate.com/recipes/tags/heap-artificial_intelligence/2015-09-17T12:41:15-07:00ActiveState Code Recipes2015-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-04-19T15:00:57-07:00jimmy2timeshttp://code.activestate.com/recipes/users/4177690/http://code.activestate.com/recipes/577661-retrieving-the-median-of-a-set-in-constant-time/

<p style="color: grey"> Python recipe 577661 by <a href="/recipes/users/4177690/">jimmy2times</a> (<a href="/recipes/tags/data/">data</a>, <a href="/recipes/tags/heap/">heap</a>, <a href="/recipes/tags/median/">median</a>, <a href="/recipes/tags/python/">python</a>, <a href="/recipes/tags/retrieving/">retrieving</a>, <a href="/recipes/tags/structure/">structure</a>). Revision 2. </p> <p>Provides a data structure for a queue of integers whose get() method returns the median element. The interface is similar to the standard Queue module, with an added method top() to retrieve the median without removing it.</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>