Lines Matching refs:heap
8 property of a heap is that a[0] is always its smallest element.
12 heap = [] # creates an empty heap
13 heappush(heap, item) # pushes a new item on the heap
14 item = heappop(heap) # pops the smallest item from the heap
15 item = heap[0] # smallest item on the heap without popping it
16 heapify(x) # transforms list into a heap, in-place, in linear time
17 item = heapreplace(heap, item) # pops and returns smallest item, and adds
18 # new item; the heap size is unchanged
20 Our API differs from textbook heap algorithms as follows:
28 These two make it possible to view the heap as a regular Python list
29 without surprises: heap[0] is the smallest item, and heap.sort()
30 maintains the heap invariant!
42 property of a heap is that a[0] is always its smallest element.
68 If this heap invariant is protected at all time, index 0 is clearly
82 scheduled into the future, so they can easily go into the heap. So, a
83 heap is a good structure for implementing schedulers (this is what I
105 the last output value), it cannot fit in the heap, so the size of the
106 heap decreases. The freed memory could be cleverly reused immediately
107 for progressively building a second heap, which grows at exactly the
108 same rate the first heap is melting. When the first heap completely
113 a few applications, and I think it is good to keep a `heap' module
140 def heappush(heap, item):
141 """Push item onto heap, maintaining the heap invariant."""
142 heap.append(item)
143 _siftdown(heap, 0, len(heap)-1)
145 def heappop(heap):
146 """Pop the smallest item off the heap, maintaining the heap invariant."""
147 lastelt = heap.pop() # raises appropriate IndexError if heap is empty
148 if heap:
149 returnitem = heap[0]
150 heap[0] = lastelt
151 _siftup(heap, 0)
156 def heapreplace(heap, item):
160 more appropriate when using a fixed-size heap. Note that the value
164 if item > heap[0]:
165 item = heapreplace(heap, item)
167 returnitem = heap[0] # raises appropriate IndexError if heap is empty
168 heap[0] = item
169 _siftup(heap, 0)
172 def heappushpop(heap, item):
174 if heap and cmp_lt(heap[0], item):
175 item, heap[0] = heap[0], item
176 _siftup(heap, 0)
180 """Transform list into a heap, in-place, in O(len(x)) time."""
190 def _heappushpop_max(heap, item):
192 if heap and cmp_lt(item, heap[0]):
193 item, heap[0] = heap[0], item
194 _siftup_max(heap, 0)
239 # 'heap' is a heap at all indices >= startpos, except possibly for pos. pos
241 # heap invariant.
242 def _siftdown(heap, startpos, pos):
243 newitem = heap[pos]
248 parent = heap[parentpos]
250 heap[pos] = parent
254 heap[pos] = newitem
256 # The child indices of heap index pos are already heaps, and we want to make
257 # a heap at index pos too. We do this by bubbling the smaller child of
263 # many books write the algorithm that way. During a heap pop, the last array
286 # Building the heap by using heappush() 1000 times instead required
295 def _siftup(heap, pos):
296 endpos = len(heap)
298 newitem = heap[pos]
304 if rightpos < endpos and not cmp_lt(heap[childpos], heap[rightpos]):
307 heap[pos] = heap[childpos]
312 heap[pos] = newitem
313 _siftdown(heap, startpos, pos)
315 def _siftdown_max(heap, startpos, pos):
317 newitem = heap[pos]
322 parent = heap[parentpos]
324 heap[pos] = parent
328 heap[pos] = newitem
330 def _siftup_max(heap, pos):
332 endpos = len(heap)
334 newitem = heap[pos]
340 if rightpos < endpos and not cmp_lt(heap[rightpos], heap[childpos]):
343 heap[pos] = heap[childpos]
348 heap[pos] = newitem
349 _siftdown_max(heap, startpos, pos)
387 _heapreplace(h, s) # restore heap condition
475 heap = []
478 heappush(heap, item)
480 while heap:
481 sort.append(heappop(heap))