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

<<(item)
Alias for: push
[](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