Class: LazyPriorityQueue

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

Direct Known Subclasses

MaxPriorityQueue, MinPriorityQueue

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize(top_condition, &heap_property) ⇒ LazyPriorityQueue

Returns a new instance of LazyPriorityQueue.



9
10
11
12
13
14
15
 
# File 'lib/lazy_priority_queue.rb', line 9

def initialize(top_condition, &heap_property)
  @top = nil
  @roots = []
  @references = {}
  @top_condition = top_condition
  @heap_property = heap_property
end

Instance Method Details

#change_priority(element, new_key) ⇒ Object 



33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/lazy_priority_queue.rb', line 33

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

  unless @heap_property[test_node, node]
    raise 'Priority can only be changed to a more prioritary value.'
  end

  node.key = new_key
  node = sift_up node
  @top = select(@top, node) unless node.parent

  element
end

#delete(element) ⇒ Object 



80
81
82
83
 
# File 'lib/lazy_priority_queue.rb', line 80

def delete(element)
  change_priority element, @top_condition
  dequeue
end

#dequeue ⇒ Object Also known as: pop 



56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/lazy_priority_queue.rb', line 56

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

Returns:

  • (Boolean) 


85
86
87
 
# File 'lib/lazy_priority_queue.rb', line 85

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
28
29
 
# File 'lib/lazy_priority_queue.rb', line 17

def enqueue(element, key)
  if @references[element]
    raise 'The provided element already is in the queue.'
  end

  node = Node.new element, key, 0

  @top = @top ? select(@top, node) : node
  @roots << node
  @references[element] = node

  element
end

#peek ⇒ Object 



52
53
54
 
# File 'lib/lazy_priority_queue.rb', line 52

def peek
  @top && @top.element
end

#size ⇒ Object Also known as: length 



89
90
91
 
# File 'lib/lazy_priority_queue.rb', line 89

def size
  @references.size
end