Please give feedback on two proposed new functions heappushpop(heap, item) and heapiter(heap). Both are intended to make the API more closely fit the way heaps are actually used and to take maximum advantage of the implementation. The first is equivalent to: def heappushpop(heap, item): "Pushes the item onto the heap and then pops the smallest value" if not heap or item < heap[0]: return item return heapreplace(heap, item) def heapiter(heap): "Return a destructive iterator over the heap's elements, smallest-to-largest" try: while 1: yield heappop(heap) except IndexError: pass Raymond
Raymond Hettinger wrote:
def heappushpop(heap, item): “Pushes the item onto the heap and then pops the smallest value”
if not heap or item < heap[0]: return item return heapreplace(heap, item) Better is: if heap and heap[0] < item: return heapreplace(heap, item) return item -- Don't touch the heap unless necessary.
-- -- Scott David Daniels Scott.Daniels@Acm.Org
Raymond Hettinger wrote:
def heappushpop(heap, item): Pushes the item onto the heap and then pops the smallest value
if not heap or item < heap[0]: return item return heapreplace(heap, item)
Scott David Daniels wrote:
Better is: if heap and heap[0] < item: return heapreplace(heap, item) return item
The or method short-circuits too.
heap = [] not heap or 7 < heap[0] 1
- Josiah
Josiah Carlson wrote:
Scott David Daniels wrote:
Better is: if heap and heap[0] < item: return heapreplace(heap, item) return item
The or method short-circuits too.
heap = [] not heap or 7 < heap[0]
Ah, but the point was to avoid the heapreplace call on equal values, not to get the shortcircuiting. Since < is the primitive-of-choice, I reversed the test. -Scott David Daniels Scott.Daniels@Acm.Org
Hello Raymond, On Sat, Jun 12, 2004 at 04:38:56AM -0400, Raymond Hettinger wrote:
def heapiter(heap): "Return a destructive iterator over the heap's elements, smallest-to-largest"
Is there a reason why the heap cannot simply be made iterable? The suggested heapiter() is destructive, but e.g. sys.stdin is also destructively iterable, so that would not be unprecedented. Alternatively, would a non-destructive algorithm be significantly slower or bad for some other reason? Armin
participants (5)
-
Armin Rigo -
Josiah Carlson -
Raymond Hettinger -
Scott David Daniels -
Scott David Daniels