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, #empty?, #initialize, #peek, #pop, #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))

Returns:

Raises:

  • (ArgumentError)

    if the element heap is not in the heap


236
237
238
239
240
241
242
243
244
# File 'lib/pairing_heap.rb', line 236

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