def __next__(self):
try:
self.dt = advance_iterator(self.gen)
except StopIteration:
if self.genlist[0] is self:
heapq.heappop(self.genlist)
else:
self.genlist.remove(self)
heapq.heapify(self.genlist)
python类heapify()的实例源码
def _iter(self):
rlist = []
self._rdate.sort()
self._genitem(rlist, iter(self._rdate))
for gen in [iter(x) for x in self._rrule]:
self._genitem(rlist, gen)
exlist = []
self._exdate.sort()
self._genitem(exlist, iter(self._exdate))
for gen in [iter(x) for x in self._exrule]:
self._genitem(exlist, gen)
lastdt = None
total = 0
heapq.heapify(rlist)
heapq.heapify(exlist)
while rlist:
ritem = rlist[0]
if not lastdt or lastdt != ritem.dt:
while exlist and exlist[0] < ritem:
exitem = exlist[0]
advance_iterator(exitem)
if exlist and exlist[0] is exitem:
heapq.heapreplace(exlist, exitem)
if not exlist or ritem != exlist[0]:
total += 1
yield ritem.dt
lastdt = ritem.dt
advance_iterator(ritem)
if rlist and rlist[0] is ritem:
heapq.heapreplace(rlist, ritem)
self._len = total
def create_binary_tree(self):
"""
Create a binary Huffman tree using stored vocabulary word counts. Frequent words
will have shorter binary codes. Called internally from `build_vocab()`.
"""
logger.info("constructing a huffman tree from %i words" % len(self.vocab))
# build the huffman tree
heap = list(itervalues(self.vocab))
heapq.heapify(heap)
for i in xrange(len(self.vocab) - 1):
min1, min2 = heapq.heappop(heap), heapq.heappop(heap)
heapq.heappush(heap, Vocab(count=min1.count + min2.count, index=i + len(self.vocab), left=min1, right=min2))
# recurse over the tree, assigning a binary code to each vocabulary word
if heap:
max_depth, stack = 0, [(heap[0], [], [])]
while stack:
node, codes, points = stack.pop()
if node.index < len(self.vocab):
# leaf node => store its path from the root
node.code, node.point = codes, points
max_depth = max(len(codes), max_depth)
else:
# inner node => continue recursion
points = array(list(points) + [node.index - len(self.vocab)], dtype=uint32)
stack.append((node.left, array(list(codes) + [0], dtype=uint8), points))
stack.append((node.right, array(list(codes) + [1], dtype=uint8), points))
logger.info("built huffman tree with maximum node depth %i" % max_depth)
def __next__(self):
try:
self.dt = advance_iterator(self.gen)
except StopIteration:
if self.genlist[0] is self:
heapq.heappop(self.genlist)
else:
self.genlist.remove(self)
heapq.heapify(self.genlist)
def _iter(self):
rlist = []
self._rdate.sort()
self._genitem(rlist, iter(self._rdate))
for gen in [iter(x) for x in self._rrule]:
self._genitem(rlist, gen)
exlist = []
self._exdate.sort()
self._genitem(exlist, iter(self._exdate))
for gen in [iter(x) for x in self._exrule]:
self._genitem(exlist, gen)
lastdt = None
total = 0
heapq.heapify(rlist)
heapq.heapify(exlist)
while rlist:
ritem = rlist[0]
if not lastdt or lastdt != ritem.dt:
while exlist and exlist[0] < ritem:
exitem = exlist[0]
advance_iterator(exitem)
if exlist and exlist[0] is exitem:
heapq.heapreplace(exlist, exitem)
if not exlist or ritem != exlist[0]:
total += 1
yield ritem.dt
lastdt = ritem.dt
advance_iterator(ritem)
if rlist and rlist[0] is ritem:
heapq.heapreplace(rlist, ritem)
self._len = total
def heap_sort():
l=[random.randint(0,100) for i in range(100)]
print l
h_l=heapq.heapify(l)
print type(h_l)
print l
print type(l)
'''
m=heapq.heappop(l)
print m
print l
'''
while len(l)!=0:
print heapq.heappop(l)
print 'done'
#basic_usage()
def solve(self):
self.path = []
if self.node_array and self.start_node and self.end_node:
closed_nodes = set()
opened_nodes = []
heapq.heapify(opened_nodes)
heapq.heappush(opened_nodes, (self.start_node.f, self.start_node))
# ??????????
while opened_nodes:
# ?????????f????node
f, node = heapq.heappop(opened_nodes)
# ???node???????, ??????
closed_nodes.add(node)
# ????????????? self.path (???????)
if node is self.end_node:
self.path = []
while node is not self.start_node:
self.path.append((node.x, node.y))
node = node.p
self.path.append((self.start_node.x, self.start_node.y))
self.path.reverse()
return # ???????
# ??????????
adj_nodes = self.get_adjacent_nodes(node)
for adj_node in adj_nodes:
# ????????, ??????
if adj_node.r and adj_node not in closed_nodes:
# ??????????????
if (adj_node.f, adj_node) in opened_nodes:
# ???????????????????????
if node.g < adj_node.g:
self.update_node(adj_node, node)
else:
# ?????????, ??????????
self.update_node(adj_node, node)
heapq.heappush(opened_nodes,
(adj_node.f, adj_node))
def __next__(self):
try:
self.dt = advance_iterator(self.gen)
except StopIteration:
if self.genlist[0] is self:
heapq.heappop(self.genlist)
else:
self.genlist.remove(self)
heapq.heapify(self.genlist)
def _iter(self):
rlist = []
self._rdate.sort()
self._genitem(rlist, iter(self._rdate))
for gen in [iter(x) for x in self._rrule]:
self._genitem(rlist, gen)
exlist = []
self._exdate.sort()
self._genitem(exlist, iter(self._exdate))
for gen in [iter(x) for x in self._exrule]:
self._genitem(exlist, gen)
lastdt = None
total = 0
heapq.heapify(rlist)
heapq.heapify(exlist)
while rlist:
ritem = rlist[0]
if not lastdt or lastdt != ritem.dt:
while exlist and exlist[0] < ritem:
exitem = exlist[0]
advance_iterator(exitem)
if exlist and exlist[0] is exitem:
heapq.heapreplace(exlist, exitem)
if not exlist or ritem != exlist[0]:
total += 1
yield ritem.dt
lastdt = ritem.dt
advance_iterator(ritem)
if rlist and rlist[0] is ritem:
heapq.heapreplace(rlist, ritem)
self._len = total
def cancel(self, event):
"""Remove an event from the queue.
This must be presented the ID as returned by enter().
If the event is not in the queue, this raises ValueError.
"""
with self._lock:
self._queue.remove(event)
heapq.heapify(self._queue)
def dijkstra(vertices, teleport_edges, source):
infinity = 10e50
dist = {v: infinity for v in vertices}
dist[source] = 0
prev = {v: None for v in vertices}
Q = []
for v in vertices:
heapq.heappush(Q, (dist[v], v))
while Q:
_, v = heapq.heappop(Q)
for v2 in vertices:
if v != v2:
d = distance(v, v2, teleport_edges)
if d is None:
continue
if dist[v] + d < dist[v2]:
dist[v2] = dist[v] + d
prev[v2] = v
#decrease-key
for i, node in enumerate(Q):
if node[1] == v2:
Q[i] = (dist[v] + d, v2)
break
heapq.heapify(Q)
return dist, prev
def dijkstra(aGraph, start):
# print '''Dijkstra's shortest path'''
# Set the distance for the start node to zero
start.set_distance(0)
# Put tuple pair into the priority queue
unvisited_queue = [(v.get_distance(), v) for v in aGraph]
heapq.heapify(unvisited_queue)
while len(unvisited_queue):
# Pops a vertex with the smallest distance
uv = heapq.heappop(unvisited_queue)
current = uv[1]
current.set_visited()
for next in current.adjacent:
# if visited, skip
if next.visited:
continue
new_dist = current.get_distance() + current.get_weight(next)
if new_dist < next.get_distance():
next.set_distance(new_dist)
next.set_previous(current)
# print 'updated : current = %s next = %s new_dist = %s' \
# %(current.get_id(), next.get_id(), str(next.get_distance()))
# else:
# print 'not updated : current = %s next = %s new_dist = %s' \
# %(current.get_id(), next.get_id(), str(next.get_distance()))
# Rebuild heap
# 1. Pop every item
while len(unvisited_queue):
heapq.heappop(unvisited_queue)
# 2. Put all vertices not visited into the queue
unvisited_queue = [(v.get_distance(), v) for v in aGraph if not v.visited]
heapq.heapify(unvisited_queue)
return
def shortest_path(digr, s):
""" Finds the shortest path from s to every other vertex findable
from s using Dijkstra's algorithm in O(mlogn) time. Uses heaps
for super fast implementation """
nodes_explored = set([s])
nodes_unexplored = DFS(digr, s) # all accessible nodes from s
nodes_unexplored.remove(s)
dist = {s:0}
node_heap = []
for n in nodes_unexplored:
min = compute_min_dist(digr, n, nodes_explored, dist)
heapq.heappush(node_heap, (min, n))
while len(node_heap) > 0:
min_dist, nearest_node = heapq.heappop(node_heap)
dist[nearest_node] = min_dist
nodes_explored.add(nearest_node)
nodes_unexplored.remove(nearest_node)
# recompute keys for just popped node
for v in digr.neighbors(nearest_node):
if v in nodes_unexplored:
for i in range(len(node_heap)):
if node_heap[i][1] == v:
node_heap[i] = (compute_min_dist(digr, v, nodes_explored, dist), v)
heapq.heapify(node_heap)
return dist
def minimum_spanning_tree(gr):
""" Uses prim's algorithm to return the minimum
cost spanning tree in a undirected connected graph.
Works only with undirected and connected graphs """
s = gr.nodes()[0]
nodes_explored = set([s])
nodes_unexplored = gr.nodes()
nodes_unexplored.remove(s)
min_cost, node_heap = 0, []
#computes the key for each vertex in unexplored
for n in nodes_unexplored:
min = compute_key(gr, n, nodes_explored)
heapq.heappush(node_heap, (min, n))
while len(nodes_unexplored) > 0:
# adds the cheapest to "explored"
node_cost, min_node = heapq.heappop(node_heap)
min_cost += node_cost
nodes_explored.add(min_node)
nodes_unexplored.remove(min_node)
# recompute keys for neighbors of deleted node
for v in gr.neighbors(min_node):
if v in nodes_unexplored:
for i in range(len(node_heap)):
if node_heap[i][1] == v:
node_heap[i] = (compute_key(gr, v, nodes_explored), v)
heapq.heapify(node_heap)
return min_cost
def create_min_heap_from(self, data):
self.min_heap = data[:]
heapq.heapify(self.min_heap)
def run(self, epochs=1):
for q in self.plugin_queues.values():
heapq.heapify(q)
for i in range(1, epochs + 1):
self.train()
self.call_plugins('epoch', i)
def _resort(self):
heapq.heapify(self.queue)
def _iter(self):
rlist = []
self._rdate.sort()
self._genitem(rlist, iter(self._rdate))
for gen in [iter(x) for x in self._rrule]:
self._genitem(rlist, gen)
exlist = []
self._exdate.sort()
self._genitem(exlist, iter(self._exdate))
for gen in [iter(x) for x in self._exrule]:
self._genitem(exlist, gen)
lastdt = None
total = 0
heapq.heapify(rlist)
heapq.heapify(exlist)
while rlist:
ritem = rlist[0]
if not lastdt or lastdt != ritem.dt:
while exlist and exlist[0] < ritem:
exitem = exlist[0]
advance_iterator(exitem)
if exlist and exlist[0] is exitem:
heapq.heapreplace(exlist, exitem)
if not exlist or ritem != exlist[0]:
total += 1
yield ritem.dt
lastdt = ritem.dt
advance_iterator(ritem)
if rlist and rlist[0] is ritem:
heapq.heapreplace(rlist, ritem)
self._len = total
def _init(self, maxsize, items=None):
if items:
self.queue = list(items)
heapq.heapify(self.queue)
else:
self.queue = []
def find_path(self, start_tiles, goal_tiles):
"""
Given a list of starting locations and a list of ending locations,
find the shortest path between them. Uses a priority queue to
do Uniform Cost Search (think Breadth First Search, but with movement
cost included).
"""
open_q = [(0, tile) for tile in start_tiles]
heapq.heapify(open_q)
goals = {tile for tile in goal_tiles}
source = defaultdict(lambda: (None, 100000000))
for tile in start_tiles:
source[tile] = (tile, 0)
while open_q:
moves, working = heapq.heappop(open_q)
for neighbor in working.get_neighbors():
if neighbor in goals:
steps = [neighbor, working]
previous = working
while source[previous][0] != previous:
previous = source[previous][0]
steps.append(previous)
return list(reversed(steps))
if not pathable(neighbor):
continue
previous_tile, previous_distance = source[neighbor]
current_distance = moves + move_cost(working, neighbor)
if current_distance < previous_distance:
source[neighbor] = (working, current_distance)
heapq.heappush(open_q, (current_distance, neighbor))
return []
