我们从Python开源项目中，提取了以下11个代码示例，用于说明如何使用heapq._siftdown()。
def dijkstra(adj, costs, s, t): ''' Return predecessors and min distance if there exists a shortest path from s to t; Otherwise, return None ''' Q = [] # priority queue of items; note item is mutable. d = {s: 0} # vertex -> minimal distance Qd = {} # vertex -> [d[v], parent_v, v] p = {} # predecessor visited_set = set([s]) for v in adj.get(s, []): d[v] = costs[s, v] item = [d[v], s, v] heapq.heappush(Q, item) Qd[v] = item while Q: print Q cost, parent, u = heapq.heappop(Q) if u not in visited_set: print 'visit:', u p[u]= parent visited_set.add(u) if u == t: return p, d[u] for v in adj.get(u, []): if d.get(v): if d[v] > costs[u, v] + d[u]: d[v] = costs[u, v] + d[u] Qd[v][0] = d[v] # decrease key Qd[v][1] = u # update predecessor heapq._siftdown(Q, 0, Q.index(Qd[v])) else: d[v] = costs[u, v] + d[u] item = [d[v], u, v] heapq.heappush(Q, item) Qd[v] = item return None
def getSkyline(self, buildings): """ :type buildings: List[List[int]] :rtype: List[List[int]] """ hs = [] heap = [] for b in buildings: hs.append((b[0], -b[2])) hs.append((b[1], b[2])) hs.sort() ans = [] pre = cur = None for h in hs: pos = h[0] height = h[1] if height < 0: heapq.heappush(heap, height) else: i = heap.index(-height) heap[i] = heap[-1] heap.pop() if i < len(heap): heapq._siftup(heap, i) heapq._siftdown(heap, 0, i) if heap: cur = heap[0] if cur != pre: ans.append((pos, -1 * cur)) pre = cur else: ans.append((pos, 0)) return ans
def pop(self): # Will remove item from the heap. value = heapq.heappop(self.heap) if self.max: value *= -1 return value # def delete(self, index): # # Magic heapify. # self.heap[index] = self.heap[-1] # Move root to index i. # self.heap.pop() # pop() last element in array O(1). # if index < len(self.heap): # Need to sift things. # # Magical internal heapify functions that does stuff in log n. # heapq._siftup(self.heap, index) # heapq._siftdown(self.heap, 0, index)
def _rank_cycle_function(self, cycle, function, ranks): """Dijkstra's shortest paths algorithm. See also: - http://en.wikipedia.org/wiki/Dijkstra's_algorithm """ import heapq Q = [] Qd = {} p = {} visited = set([function]) ranks[function] = 0 for call in compat_itervalues(function.calls): if call.callee_id != function.id: callee = self.functions[call.callee_id] if callee.cycle is cycle: ranks[callee] = 1 item = [ranks[callee], function, callee] heapq.heappush(Q, item) Qd[callee] = item while Q: cost, parent, member = heapq.heappop(Q) if member not in visited: p[member]= parent visited.add(member) for call in compat_itervalues(member.calls): if call.callee_id != member.id: callee = self.functions[call.callee_id] if callee.cycle is cycle: member_rank = ranks[member] rank = ranks.get(callee) if rank is not None: if rank > 1 + member_rank: rank = 1 + member_rank ranks[callee] = rank Qd_callee = Qd[callee] Qd_callee[0] = rank Qd_callee[1] = member heapq._siftdown(Q, 0, Q.index(Qd_callee)) else: rank = 1 + member_rank ranks[callee] = rank item = [rank, member, callee] heapq.heappush(Q, item) Qd[callee] = item
