Class: LazyPriorityQueue
- Inherits:
-
Object
show all
- Defined in:
- lib/lazy_priority_queue.rb
Defined Under Namespace
Classes: Node
Instance Method Summary
collapse
Constructor Details
#initialize(top_condition, &heap_property) ⇒ LazyPriorityQueue
Returns a new instance of LazyPriorityQueue.
10
11
12
13
14
15
|
# File 'lib/lazy_priority_queue.rb', line 10
def initialize top_condition, &heap_property
@roots = []
@references = {}
@top_condition = top_condition
@heap_property = heap_property
end
|
Instance Method Details
#change_priority(element, new_key) ⇒ Object
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
# File 'lib/lazy_priority_queue.rb', line 31
def change_priority element, new_key
node = @references[element]
raise 'Element provided is not in the queue.' unless node
test_node = node.clone
test_node.key = new_key
raise 'Priority can only be changed to a more prioritary value.' unless @heap_property[test_node, node]
node.key = new_key
node = sift_up node
@top = select(@top, node) unless node.parent
element
end
|
#delete(element) ⇒ Object
75
76
77
78
|
# File 'lib/lazy_priority_queue.rb', line 75
def delete element
change_priority element, @top_condition
dequeue
end
|
#dequeue ⇒ Object
Also known as:
pop
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
# File 'lib/lazy_priority_queue.rb', line 51
def dequeue
return unless @top
element = @top.element
@references.delete element
@roots.delete @top
child = @top.left_child
while child
next_child = child.right_sibling
child.parent = nil
child.right_sibling = nil
@roots << child
child = next_child
end
@roots = coalesce @roots
@top = @roots.inject { |top, node| select top, node }
element
end
|
#empty? ⇒ Boolean
80
|
# File 'lib/lazy_priority_queue.rb', line 80
def empty?; @references.empty? end
|
#enqueue(element, key) ⇒ Object
Also known as:
push, insert
17
18
19
20
21
22
23
24
25
26
27
|
# File 'lib/lazy_priority_queue.rb', line 17
def enqueue element, key
raise 'The provided element already is in the queue.' if @references[element]
node = Node.new element, key, 0
@top = @top ? select(@top, node) : node
@roots << node
@references[element] = node
element
end
|
#peek ⇒ Object
47
48
49
|
# File 'lib/lazy_priority_queue.rb', line 47
def peek
@top and @top.element
end
|
#size ⇒ Object
Also known as:
length
81
|
# File 'lib/lazy_priority_queue.rb', line 81
def size; @references.size end
|