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 = heapreplace(heap, item) # pops and returns smallest item, and adds
16 # new item; the heap size is unchanged
18 Our API differs from textbook heap algorithms as follows:
26 These two make it possible to view the heap as a regular Python list
27 without surprises: heap[0] is the smallest item, and heap.sort()
28 maintains the heap invariant!
40 property of a heap is that a[0] is always its smallest element.
66 If this heap invariant is protected at all time, index 0 is clearly
80 scheduled into the future, so they can easily go into the heap. So, a
81 heap is a good structure for implementing schedulers (this is what I
103 the last output value), it cannot fit in the heap, so the size of the
104 heap decreases. The freed memory could be cleverly reused immediately
105 for progressively building a second heap, which grows at exactly the
106 same rate the first heap is melting. When the first heap completely
111 a few applications, and I think it is good to keep a `heap' module
130 def heappush(heap, item):
131 """Push item onto heap, maintaining the heap invariant."""
132 heap.append(item)
133 _siftdown(heap, 0, len(heap)-1)
135 def heappop(heap):
136 """Pop the smallest item off the heap, maintaining the heap invariant."""
137 lastelt = heap.pop() # raises appropriate IndexError if heap is empty
138 if heap:
139 returnitem = heap[0]
140 heap[0] = lastelt
141 _siftup(heap, 0)
145 def heapreplace(heap, item):
149 more appropriate when using a fixed-size heap. Note that the value
153 if item > heap[0]:
154 item = heapreplace(heap, item)
156 returnitem = heap[0] # raises appropriate IndexError if heap is empty
157 heap[0] = item
158 _siftup(heap, 0)
161 def heappushpop(heap, item):
163 if heap and heap[0] < item:
164 item, heap[0] = heap[0], item
165 _siftup(heap, 0)
169 """Transform list into a heap, in-place, in O(len(x)) time."""
179 def _heappop_max(heap):
181 lastelt = heap.pop() # raises appropriate IndexError if heap is empty
182 if heap:
183 returnitem = heap[0]
184 heap[0] = lastelt
185 _siftup_max(heap, 0)
189 def _heapreplace_max(heap, item):
191 returnitem = heap[0] # raises appropriate IndexError if heap is empty
192 heap[0] = item
193 _siftup_max(heap, 0)
202 # 'heap' is a heap at all indices >= startpos, except possibly for pos. pos
204 # heap invariant.
205 def _siftdown(heap, startpos, pos):
206 newitem = heap[pos]
211 parent = heap[parentpos]
213 heap[pos] = parent
217 heap[pos] = newitem
219 # The child indices of heap index pos are already heaps, and we want to make
220 # a heap at index pos too. We do this by bubbling the smaller child of
226 # many books write the algorithm that way. During a heap pop, the last array
249 # Building the heap by using heappush() 1000 times instead required
258 def _siftup(heap, pos):
259 endpos = len(heap)
261 newitem = heap[pos]
267 if rightpos < endpos and not heap[childpos] < heap[rightpos]:
270 heap[pos] = heap[childpos]
275 heap[pos] = newitem
276 _siftdown(heap, startpos, pos)
278 def _siftdown_max(heap, startpos, pos):
280 newitem = heap[pos]
285 parent = heap[parentpos]
287 heap[pos] = parent
291 heap[pos] = newitem
293 def _siftup_max(heap, pos):
295 endpos = len(heap)
297 newitem = heap[pos]
303 if rightpos < endpos and not heap[rightpos] < heap[childpos]:
306 heap[pos] = heap[childpos]
311 heap[pos] = newitem
312 _siftdown_max(heap, startpos, pos)
360 _heapreplace(h, s) # restore heap condition
399 # in a heap. Memory consumption is limited to keeping k values in a list.
417 # 2 n - k compare remaining elements to top of heap
418 # 3 k * (1 + lg2(k)) * ln(n/k) replace the topmost value on the heap
431 # heap is 1 + log(k, 2).
448 # must be inserted in the heap: