Lines Matching refs:heap
6 property of a heap is that a[0] is always its smallest element.
10 heap = [] # creates an empty heap
11 heappush(heap, item) # pushes a new item on the heap
12 item = heappop(heap) # pops the smallest item from the heap
13 item = heap[0] # smallest item on the heap without popping it
14 heapify(x) # transforms list into a heap, in-place, in linear time
15 item = heappushpop(heap, item) # pushes a new item and then returns
16 # the smallest item; the heap size is unchanged
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
132 def heappush(heap, item):
133 """Push item onto heap, maintaining the heap invariant."""
134 heap.append(item)
135 _siftdown(heap, 0, len(heap)-1)
137 def heappop(heap):
138 """Pop the smallest item off the heap, maintaining the heap invariant."""
139 lastelt = heap.pop() # raises appropriate IndexError if heap is empty
140 if heap:
141 returnitem = heap[0]
142 heap[0] = lastelt
143 _siftup(heap, 0)
147 def heapreplace(heap, item):
151 more appropriate when using a fixed-size heap. Note that the value
155 if item > heap[0]:
156 item = heapreplace(heap, item)
158 returnitem = heap[0] # raises appropriate IndexError if heap is empty
159 heap[0] = item
160 _siftup(heap, 0)
163 def heappushpop(heap, item):
165 if heap and heap[0] < item:
166 item, heap[0] = heap[0], item
167 _siftup(heap, 0)
171 """Transform list into a heap, in-place, in O(len(x)) time."""
181 def _heappop_max(heap):
183 lastelt = heap.pop() # raises appropriate IndexError if heap is empty
184 if heap:
185 returnitem = heap[0]
186 heap[0] = lastelt
187 _siftup_max(heap, 0)
191 def _heapreplace_max(heap, item):
193 returnitem = heap[0] # raises appropriate IndexError if heap is empty
194 heap[0] = item
195 _siftup_max(heap, 0)
204 # 'heap' is a heap at all indices >= startpos, except possibly for pos. pos
206 # heap invariant.
207 def _siftdown(heap, startpos, pos):
208 newitem = heap[pos]
213 parent = heap[parentpos]
215 heap[pos] = parent
219 heap[pos] = newitem
221 # The child indices of heap index pos are already heaps, and we want to make
222 # a heap at index pos too. We do this by bubbling the smaller child of
228 # many books write the algorithm that way. During a heap pop, the last array
251 # Building the heap by using heappush() 1000 times instead required
260 def _siftup(heap, pos):
261 endpos = len(heap)
263 newitem = heap[pos]
269 if rightpos < endpos and not heap[childpos] < heap[rightpos]:
272 heap[pos] = heap[childpos]
277 heap[pos] = newitem
278 _siftdown(heap, startpos, pos)
280 def _siftdown_max(heap, startpos, pos):
282 newitem = heap[pos]
287 parent = heap[parentpos]
289 heap[pos] = parent
293 heap[pos] = newitem
295 def _siftup_max(heap, pos):
297 endpos = len(heap)
299 newitem = heap[pos]
305 if rightpos < endpos and not heap[rightpos] < heap[childpos]:
308 heap[pos] = heap[childpos]
313 heap[pos] = newitem
314 _siftdown_max(heap, startpos, pos)
362 _heapreplace(h, s) # restore heap condition
401 # in a heap. Memory consumption is limited to keeping k values in a list.
419 # 2 n - k compare remaining elements to top of heap
420 # 3 k * (1 + lg2(k)) * ln(n/k) replace the topmost value on the heap
433 # heap is 1 + log(k, 2).
450 # must be inserted in the heap: