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
 
# File 'lib/new_relic/agent/heap.rb', line 26

def initialize(items = nil, &priority_fn)
  @items = []
  @priority_fn = priority_fn || ->(x) { x }
  items&.each { |item| push(item) }
end

Instance Method Details

#[](index) ⇒ Object 



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

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

#[]=(index, value) ⇒ Object 



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

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

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


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

def empty?
  @items.empty?
end

#fix(index) ⇒ Object 



40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/new_relic/agent/heap.rb', line 40

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 



67
68
69
70
71
72
 
# File 'lib/new_relic/agent/heap.rb', line 67

def pop
  swap(0, size - 1)
  item = @items.pop
  heapify_down(0)
  item
end

#push(item) ⇒ Object Also known as: << 



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

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

#size ⇒ Object 



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

def size
  @items.size
end

#to_a ⇒ Object 



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

def to_a
  @items
end