class NewRelic::Agent::Heap
This class implements a min Heap
. The first element is always the one with the lowest priority. It is a tree structure that is represented as an array. The relationship between nodes in the tree and indices in the array are as follows:
parent_index = (child_index - 1) / 2 left_child_index = parent_index * 2 + 1 right_child_index = parent_index * 2 + 2
the root node is at index 0 a node is a leaf node when its index >= length / 2
Public Class Methods
new(items = nil, &priority_fn)
click to toggle source
@param [Array] items an optional array of items to initialize the heap
@param [Callable] priority_fn an optional priority function used to
to compute the priority for an item. If it's not supplied priority will be computed using Comparable.
# File lib/new_relic/agent/heap.rb, line 26 def initialize(items = nil, &priority_fn) @items = [] @priority_fn = priority_fn || ->(x) { x } # the following line needs else branch coverage items.each { |item| push(item) } if items # rubocop:disable Style/SafeNavigation end
Public Instance Methods
[](index)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 33 def [](index) @items[index] end
[]=(index, value)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 37 def []=(index, value) @items[index] = value end
empty?()
click to toggle source
# File lib/new_relic/agent/heap.rb, line 79 def empty? @items.empty? end
fix(index)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 41 def fix(index) parent_index = parent_index_for(index) if in_range?(parent_index) && priority(parent_index) > priority(index) heapify_up(index) else child_index = left_child_index_for(index) return unless in_range?(child_index) if right_sibling_smaller?(child_index) child_index += 1 end if priority(child_index) < priority(index) heapify_down(index) end end end
pop()
click to toggle source
# File lib/new_relic/agent/heap.rb, line 68 def pop swap(0, size - 1) item = @items.pop heapify_down(0) item end
push(item)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 61 def push(item) @items << item heapify_up(size - 1) end
Also aliased as: <<
size()
click to toggle source
# File lib/new_relic/agent/heap.rb, line 75 def size @items.size end
to_a()
click to toggle source
# File lib/new_relic/agent/heap.rb, line 83 def to_a @items end
Private Instance Methods
heapify_down(parent_index)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 120 def heapify_down(parent_index) child_index = left_child_index_for(parent_index) return unless in_range?(child_index) if right_sibling_smaller?(child_index) child_index += 1 end if priority(child_index) < priority(parent_index) swap(parent_index, child_index) heapify_down(child_index) end end
heapify_up(child_index)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 109 def heapify_up(child_index) return if child_index == 0 parent_index = parent_index_for(child_index) if priority(child_index) < priority(parent_index) swap(child_index, parent_index) heapify_up(parent_index) end end
in_range?(index)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 105 def in_range?(index) index >= 0 && index < size end
left_child_index_for(parent_index)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 97 def left_child_index_for(parent_index) parent_index * 2 + 1 end
parent_index_for(child_index)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 93 def parent_index_for(child_index) (child_index - 1) / 2 end
priority(index)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 89 def priority(index) @priority_fn.call(@items[index]) end
right_sibling_smaller?(lchild_index)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 101 def right_sibling_smaller?(lchild_index) in_range?(lchild_index + 1) && priority(lchild_index) > priority(lchild_index + 1) end
swap(i, j)
click to toggle source
# File lib/new_relic/agent/heap.rb, line 134 def swap(i, j) @items[i], @items[j] = @items[j], @items[i] end