Class: DeadEnd::PriorityQueue

Inherits:
Object
  • Object
show all
Defined in:
lib/dead_end/priority_queue.rb

Overview

Holds elements in a priority heap on insert

Instead of constantly calling ‘sort!`, put the element where it belongs the first time around

Example:

queue = PriorityQueue.new
queue << 33
queue << 44
queue << 1

puts queue.peek # => 44

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ PriorityQueue

Returns a new instance of PriorityQueue.



22
23
24
 
# File 'lib/dead_end/priority_queue.rb', line 22

def initialize
  @elements = []
end

Instance Attribute Details

#elements ⇒ Object (readonly)

Returns the value of attribute elements.



20
21
22
 
# File 'lib/dead_end/priority_queue.rb', line 20

def elements
  @elements
end

Instance Method Details

#<<(element) ⇒ Object 



26
27
28
29
 
# File 'lib/dead_end/priority_queue.rb', line 26

def <<(element)
  @elements << element
  bubble_up(last_index, element)
end

#empty? ⇒ Boolean

Returns:

  • (Boolean) 


42
43
44
 
# File 'lib/dead_end/priority_queue.rb', line 42

def empty?
  @elements.empty?
end

#exchange(source, target) ⇒ Object 



98
99
100
101
102
103
 
# File 'lib/dead_end/priority_queue.rb', line 98

def exchange(source, target)
  a = @elements[source]
  b = @elements[target]
  @elements[source] = b
  @elements[target] = a
end

#length ⇒ Object 



38
39
40
 
# File 'lib/dead_end/priority_queue.rb', line 38

def length
  @elements.length
end

#peek ⇒ Object 



46
47
48
 
# File 'lib/dead_end/priority_queue.rb', line 46

def peek
  @elements.first
end

#pop ⇒ Object 



31
32
33
34
35
36
 
# File 'lib/dead_end/priority_queue.rb', line 31

def pop
  exchange(0, last_index)
  max = @elements.pop
  bubble_down(0)
  max
end

#sorted ⇒ Object

Used for testing, extremely not performant



55
56
57
58
59
60
61
62
63
 
# File 'lib/dead_end/priority_queue.rb', line 55

def sorted
  out = []
  elements = @elements.dup
  while (element = pop)
    out << element
  end
  @elements = elements
  out.reverse
end

#to_a ⇒ Object 



50
51
52
 
# File 'lib/dead_end/priority_queue.rb', line 50

def to_a
  @elements
end