Method _siftup

networkx/utils/mapped_queue.py:239–276

Move smaller child up until hitting a leaf. Built to mimic code for heapq._siftup only updating position dict too.

(self, pos)

        self._siftup(pos)

    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

    def _siftdown(self, start_pos, pos):
        """Restore invariant. keep swapping with parent until smaller.