Class: PairingHeap::SafeChangePriorityQueue
- Inherits:
-
PairingHeap
- Object
- PairingHeap
- PairingHeap::SafeChangePriorityQueue
- Defined in:
- lib/pairing_heap.rb
Overview
Priority queue with change_priority, that accepts changing to a less prioritary priority
Instance Method Summary collapse
-
#change_priority(elem, priority) ⇒ PairingHeap
Changes a priority of the element to a more prioritary one Time Complexity: O(N) Amortized Time Complexity: O(log(N)).
Methods inherited from PairingHeap
#any?, #delete, #empty?, #initialize, #peek, #peek_priority, #pop, #pop_priority, #push, #size
Constructor Details
This class inherits a constructor from PairingHeap::PairingHeap
Instance Method Details
#change_priority(elem, priority) ⇒ PairingHeap
Changes a priority of the element to a more prioritary one
Time Complexity: O(N)
Amortized Time Complexity: O(log(N))
355 356 357 358 359 360 361 362 363 |
# File 'lib/pairing_heap.rb', line 355 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 |