http://code.activestate.com/recipes/tags/heapq-top/2013-12-08T21:12:55-08: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>

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-07-25T23:42:21-07:00Giampaolo Rodolàhttp://code.activestate.com/recipes/users/4178764/http://code.activestate.com/recipes/577808-asyncore-scheduler/

<p style="color: grey"> Python recipe 577808 by <a href="/recipes/users/4178764/">Giampaolo Rodolà</a> (<a href="/recipes/tags/asynchronous/">asynchronous</a>, <a href="/recipes/tags/asyncore/">asyncore</a>, <a href="/recipes/tags/heapq/">heapq</a>, <a href="/recipes/tags/nonblocking/">nonblocking</a>, <a href="/recipes/tags/scheduler/">scheduler</a>, <a href="/recipes/tags/twisted/">twisted</a>). Revision 5. </p> <p>The thing I miss mostly in asyncore is a system for calling a function after a certain amount of time without blocking. This is crucial for simple tasks such as disconnecting a peer after a certain time of inactivity or more advanced use cases such as <a href="http://code.google.com/p/pyftpdlib/source/browse/tags/release-0.6.0/pyftpdlib/ftpserver.py#1048">bandwidth throttling</a>.</p> <p>This recipe was initially inspired by Twisted's internet.base.DelayedCall class:</p> <p><a href="http://twistedmatrix.com/trac/browser/tags/last_vfs_and_web2/twisted/internet/base.py#L34" rel="nofollow">http://twistedmatrix.com/trac/browser/tags/last_vfs_and_web2/twisted/internet/base.py#L34</a></p> <p>...then included into pyftpdlib:</p> <p><a href="http://code.google.com/p/pyftpdlib/issues/detail?id=72" rel="nofollow">http://code.google.com/p/pyftpdlib/issues/detail?id=72</a></p> <p>...and finally proposed for inclusion into asyncore:</p> <p><a href="http://bugs.python.org/issue1641" rel="nofollow">http://bugs.python.org/issue1641</a></p>