Popular recipes tagged "heapq"http://code.activestate.com/recipes/tags/heapq/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> asyncore scheduler (Python) 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> Handling ties for top largest/smallest elements (Python) 2009-04-07T18:57:35-07:00George Sakkishttp://code.activestate.com/recipes/users/2591466/http://code.activestate.com/recipes/576712-handling-ties-for-top-largestsmallest-elements/ <p style="color: grey"> Python recipe 576712 by <a href="/recipes/users/2591466/">George Sakkis</a> (<a href="/recipes/tags/heapq/">heapq</a>, <a href="/recipes/tags/largest/">largest</a>, <a href="/recipes/tags/smallest/">smallest</a>, <a href="/recipes/tags/top/">top</a>). Revision 8. </p> <p>The heapq module provides efficient functions for getting the top-N smallest and largest elements of an iterable. A caveat of these functions is that if there are ties (i.e. equal elements with respect to the comparison key), some elements may end up in the returned top-N list while some equal others may not:</p> <pre class="prettyprint"><code>&gt;&gt;&gt; nsmallest(3, [4,3,-2,-3,2], key=abs) [-2, 2, 3] </code></pre> <p>Although 3 and -3 are equal with respect to the key function, only one of them is chosen to be returned. For several applications, an all-or-nothing approach with respect to ties is preferable or even required.</p> <p>A new optional boolean parameter 'ties' is proposed to accomodate these cases. If ties=True and the iterable contains more than N elements, the length of the returned sorted list can be lower than N if not all ties at the last position can fit in the list:</p> <pre class="prettyprint"><code>&gt;&gt;&gt; nsmallest(3, [4,3,-2,-3,2], key=abs, ties=True) [-2, 2] </code></pre>