class LazyPriorityQueue
Constants
- Node
Public Class Methods
new(top_condition, &heap_property)
click to toggle source
# 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
Public Instance Methods
change_priority(element, new_key)
click to toggle source
# 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)
click to toggle source
# File lib/lazy_priority_queue.rb, line 80 def delete(element) change_priority element, @top_condition dequeue end
dequeue()
click to toggle source
# 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
Also aliased as: pop
empty?()
click to toggle source
# File lib/lazy_priority_queue.rb, line 85 def empty? @references.empty? end
enqueue(element, key)
click to toggle source
# 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()
click to toggle source
# File lib/lazy_priority_queue.rb, line 52 def peek @top && @top.element end
size()
click to toggle source
# File lib/lazy_priority_queue.rb, line 89 def size @references.size end
Also aliased as: length
Private Instance Methods
add(node_one, node_two)
click to toggle source
# File lib/lazy_priority_queue.rb, line 129 def add(node_one, node_two) if node_one.rank != node_two.rank raise 'Both nodes must hold the same rank.' end if node_one.parent || node_two.parent raise 'Both nodes must be roots (no parents).' end adder_node, addend_node = if @heap_property[node_one, node_two] [node_one, node_two] else [node_two, node_one] end addend_node.parent = adder_node # This line must go before than... addend_node.right_sibling = adder_node.left_child # ...this one. adder_node.left_child = addend_node adder_node.rank += 1 adder_node end
coalesce(trees)
click to toggle source
# File lib/lazy_priority_queue.rb, line 112 def coalesce(trees) coalesced_trees = [] while tree = trees.pop if coalesced_tree = coalesced_trees[tree.rank] # This line must go before than... coalesced_trees[tree.rank] = nil # ...this one. trees << add(tree, coalesced_tree) else coalesced_trees[tree.rank] = tree end end coalesced_trees.compact end
select(parent_node, child_node)
click to toggle source
# File lib/lazy_priority_queue.rb, line 108 def select(parent_node, child_node) @heap_property[parent_node, child_node] ? parent_node : child_node end
sift_up(node)
click to toggle source
# File lib/lazy_priority_queue.rb, line 96 def sift_up(node) return node unless node.parent && !@heap_property[node.parent, node] node.parent.key, node.key = node.key, node.parent.key node.parent.element, node.element = node.element, node.parent.element @references[node.element] = node @references[node.parent.element] = node.parent sift_up node.parent end