Class: NewRelic::Agent::Heap

Inherits:
Object
  • Object
show all
Defined in:
lib/new_relic/agent/heap.rb

Overview

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

Instance Method Summary collapse

Constructor Details

#initialize(items = nil, &priority_fn) ⇒ Heap

Returns a new instance of Heap.

Parameters:

  • items (Array) (defaults to: nil) —

    an optional array of items to initialize the heap

  • priority_fn (Callable) —

    an optional priority function used to to compute the priority for an item. If it’s not supplied priority will be computed using Comparable.



26
27
28
29
30
31
 
# 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

Instance Method Details

#[](index) ⇒ Object 



33
34
35
 
# File 'lib/new_relic/agent/heap.rb', line 33

def [](index)
  @items[index]
end

#[]=(index, value) ⇒ Object 



37
38
39
 
# File 'lib/new_relic/agent/heap.rb', line 37

def []=(index, value)
  @items[index] = value
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


79
80
81
 
# File 'lib/new_relic/agent/heap.rb', line 79

def empty?
  @items.empty?
end

#fix(index) ⇒ Object 



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# 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 ⇒ Object 



68
69
70
71
72
73
 
# 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) ⇒ Object Also known as: << 



61
62
63
64
 
# File 'lib/new_relic/agent/heap.rb', line 61

def push(item)
  @items << item
  heapify_up(size - 1)
end

#size ⇒ Object 



75
76
77
 
# File 'lib/new_relic/agent/heap.rb', line 75

def size
  @items.size
end

#to_a ⇒ Object 



83
84
85
 
# File 'lib/new_relic/agent/heap.rb', line 83

def to_a
  @items
end