class_docstr: The MappedQueue class implements a min-heap with removal and update-priority.
  
  The min heap uses heapq as well as custom written _siftup and _siftdown
  methods to allow the heap positions to be tracked by an additional dict
  keyed by element to position. The smallest element can be popped in O(1) time,
  new elements can be pushed in O(log n) time, and any element can be removed
  or updated in O(log n) time. The queue cannot contain duplicate elements
  and an attempt to push an element already in the queue will have no effect.
  
  MappedQueue complements the heapq package from the python standard
  library. While MappedQueue is designed for maximum compatibility with
  heapq, it adds element removal, lookup, and priority update.
  
  Parameters
  ----------
  data : dict or iterable
  
  Examples
  --------
  
  A `MappedQueue` can be created empty, or optionally, given a dictionary
  of initial elements and priorities.  The methods `push`, `pop`,
  `remove`, and `update` operate on the queue.
  
  >>> colors_nm = {'red':665, 'blue': 470, 'green': 550}
  >>> q = MappedQueue(colors_nm)
  >>> q.remove('red')
  >>> q.update('green', 'violet', 400)
  >>> q.push('indigo', 425)
  True
  >>> [q.pop().element for i in range(len(q.heap))]
  ['violet', 'indigo', 'blue']
  
  A `MappedQueue` can also be initialized with a list or other iterable. The priority is assumed
  to be the sort order of the items in the list.
  
  >>> q = MappedQueue([916, 50, 4609, 493, 237])
  >>> q.remove(493)
  >>> q.update(237, 1117)
  >>> [q.pop() for i in range(len(q.heap))]
  [50, 916, 1117, 4609]
  
  An exception is raised if the elements are not comparable.
  
  >>> q = MappedQueue([100, 'a'])
  Traceback (most recent call last):
  ...
  TypeError: '<' not supported between instances of 'int' and 'str'
  
  To avoid the exception, use a dictionary to assign priorities to the elements.
  
  >>> q = MappedQueue({100: 0, 'a': 1 })
  
  References
  ----------
  .. [1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001).
     Introduction to algorithms second edition.
  .. [2] Knuth, D. E. (1997). The art of computer programming (Vol. 3).
     Pearson Education.
class_docstr_tok: ["The","MappedQueue","class","implements","a","min-heap","with","removal","and","update-priority",".","The","min","heap","uses","heapq","as","well","as","custom","written","_siftup","and","_siftdown","methods","to","allow","the","heap","positions","to","be","tracked","by","an","additional","dict","keyed","by","element","to","position",".","The","smallest","element","can","be","popped","in","O","(","1",")","time",",","new","elements","can","be","pushed","in","O","(","log","n",")","time",",","and","any","element","can","be","removed","or","updated","in","O","(","log","n",")","time",".","The","queue","can","not","contain","duplicate","elements","and","an","attempt","to","push","an","element","already","in","the","queue","will","have","no","effect",".","MappedQueue","complements","the","heapq","package","from","the","python","standard","library",".","While","MappedQueue","is","designed","for","maximum","compatibility","with","heapq",",","it","adds","element","removal",",","lookup",",","and","priority","update",".","Parameters","--","--","--","--","--","data",":","dict","or","iterable","Examples","--","--","--","--","A","`","MappedQueue","`","can","be","created","empty",",","or","optionally",",","given","a","dictionary","of","initial","elements","and","priorities",".","The","methods","`","push","`",",","`","pop","`",",","`","remove","`",",","and","`","update","`","operate","on","the","queue",".",">",">",">","colors_nm","=","{","'red':665",",","'blue","'",":","470",",","'green","'",":","550","}",">",">",">","q","=","MappedQueue","(","colors_nm",")",">",">",">","q.remove","(","'red","'",")",">",">",">","q.update","(","'green","'",",","'violet","'",",","400",")",">",">",">","q.push","(","'indigo","'",",","425",")","True",">",">",">","[","q.pop","(",")",".element","for","i","in","range","(","len","(","q.heap",")",")","]","[","'violet","'",",","'indigo","'",",","'blue","'","]","A","`","MappedQueue","`","can","also","be","initialized","with","a","list","or","other","iterable",".","The","priority","is","assumed","to","be","the","sort","order","of","the","items","in","the","list",".",">",">",">","q","=","MappedQueue","(","[","916",",","50",",","4609",",","493",",","237","]",")",">",">",">","q.remove","(","493",")",">",">",">","q.update","(","237",",","1117",")",">",">",">","[","q.pop","(",")","for","i","in","range","(","len","(","q.heap",")",")","]","[","50",",","916",",","1117",",","4609","]","An","exception","is","raised","if","the","elements","are","not","comparable",".",">",">",">","q","=","MappedQueue","(","[","100",",","'","a","'","]",")","Traceback","(","most","recent","call","last",")",":","...","TypeError",":","'","<","'","not","supported","between","instances","of","'int","'","and","'str'","To","avoid","the","exception",",","use","a","dictionary","to","assign","priorities","to","the","elements",".",">",">",">","q","=","MappedQueue","(","{","100",":","0",",","'","a","'",":","1","}",")","References","--","--","--","--","--","..","[","1","]","Cormen",",","T.","H.",",","Leiserson",",","C.","E.",",","Rivest",",","R.","L.",",","&","Stein",",","C.","(","2001",")",".","Introduction","to","algorithms","second","edition",".","..","[","2","]","Knuth",",","D.","E.","(","1997",")",".","The","art","of","computer","programming","(","Vol",".","3",")",".","Pearson","Education","."]
docstr: Move smaller child up until hitting a leaf.
  
  Built to mimic code for heapq._siftup
  only updating position dict too.
docstr_tok: ["Move","smaller","child","up","until","hitting","a","leaf",".","Built","to","mimic","code","for","heapq._siftup","only","updating","position","dict","too","."]
code: def _siftup(self, pos):
      """Move smaller child up until hitting a leaf.
  
      Built to mimic code for heapq._siftup
      only updating position dict too.
      """
      heap, position = self.heap, self.position
      end_pos = len(heap)
      startpos = pos
      newitem = heap[pos]
      # Shift up the smaller child until hitting a leaf
      child_pos = (pos << 1) + 1  # start with leftmost child position
      while child_pos < end_pos:
          # Set child_pos to index of smaller child.
          child = heap[child_pos]
          right_pos = child_pos + 1
          if right_pos < end_pos:
              right = heap[right_pos]
              if not child < right:
                  child = right
                  child_pos = right_pos
          # Move the smaller child up.
          heap[pos] = child
          position[child] = pos
          pos = child_pos
          child_pos = (pos << 1) + 1
      # pos is a leaf position. Put newitem there, and bubble it up
      # to its final resting place (by sifting its parents down).
      while pos > 0:
          parent_pos = (pos - 1) >> 1
          parent = heap[parent_pos]
          if not newitem < parent:
              break
          heap[pos] = parent
          position[parent] = pos
          pos = parent_pos
      heap[pos] = newitem
      position[newitem] = pos
  
file_path: networkx/networkx/utils/mapped_queue.py
imports: import heapq
label_desc: Use image node_id 8 for calling the MappedQueue obj's underlying member method code with example usage: obj._siftup(pos) without return types