Method: CompSci::Heap#sift_down

Defined in:
lib/compsci/heap.rb

#sift_down(idx) ⇒ Object

  • called recursively

  • idx represents the node suspected to violate the heap

  • intended to be O(log n) on heap size (log base child_slots)

  • slower than sift_up because one parent vs multiple children



81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/compsci/heap.rb', line 81

def sift_down(idx)
  return self if idx >= @array.size
  cidxs = self.class.children_idx(idx, @child_slots)
  # promote the heapiest child
  cidx = self.heapiest(cidxs)
  if !self.heapish?(idx, cidx)
    @array[idx], @array[cidx] = @array[cidx], @array[idx]   # swap
    self.sift_down(cidx)
  end
  self
end