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, #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))

Returns:

Raises:

  • (ArgumentError)

    if the element heap is not in the heap


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