Class: PairingHeap::SafeChangePriorityQueue

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

Overview

Priority queue with change_priority, that accepts changing to a less prioritary priority

Instance Method Summary collapse

Methods inherited from PairingHeap

#any?, #delete, #each, #each_with_priority, #empty?, #get_priority, #get_priority_if_exists, #include?, #initialize, #peek, #peek_priority, #peek_with_priority, #pop, #pop_priority, #pop_with_priority, #push, #size

Constructor Details

This class inherits a constructor from PairingHeap::PairingHeap

Instance Method Details

#change_priority(elem, priority) ⇒ self

Changes a priority of the element

Time Complexity: O(N)
Amortized Time Complexity: O(log(N))

Returns:

  • (self)

Raises:

  • (ArgumentError) —

    if the element is not in the heap



475
476
477
478
479
480
481
482
483
 
# File 'lib/pairing_heap.rb', line 475

def change_priority(elem, priority)
  raise ArgumentError, "Provided element is not in heap" unless @nodes.key?(elem)
  if !@order[priority, @nodes[elem].priority]
    delete(elem)
    push(elem, priority)
  else
    super(elem, priority)
  end
end