Method: CompSci::Heap#sift_up

Defined in:
lib/compsci/heap.rb

#sift_up(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)



66
67
68
69
70
71
72
73
74
 
# File 'lib/compsci/heap.rb', line 66

def sift_up(idx)
  return self if idx <= 0
  pidx = self.class.parent_idx(idx, @child_slots)
  if !self.heapish?(pidx, idx)
    @array[idx], @array[pidx] = @array[pidx], @array[idx]   # swap
    self.sift_up(pidx)
  end
  self
end