class PairingHeap::PairingHeap

Pairing heap data structure implementation @see en.wikipedia.org/wiki/Pairing_heap

Public Class Methods

new(&block) click to toggle source

@yield [l_priority, r_priority] Optional heap property priority comparator. ‘<:=.to_proc` by default @yieldreturn [boolean] if `l_priority` is more prioritary than `r_priority`, or the priorities are equal

# File lib/pairing_heap.rb, line 75
def initialize(&block)
  @root = nil
  @nodes = {}
  @order = block || :<=.to_proc
end

Public Instance Methods

any?() click to toggle source

Time Complexity: O(1) @return [Boolean]

# File lib/pairing_heap.rb, line 130
def any?
  !@root.nil?
end
change_priority(elem, priority) click to toggle source

Changes a priority of element to a more prioritary one

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

@param elem Element @param priority New priority @raise [ArgumentError] if the element is not in the heap or the new priority is less prioritary @return [self]

# File lib/pairing_heap.rb, line 186
def change_priority(elem, priority)
  node = @nodes[elem]
  raise ArgumentError, "Provided element is not in heap" if node.nil?
  unless @order[priority, node.priority]
    raise ArgumentError, "Priority cannot be changed to a less prioritary value."
  end

  node.priority = priority
  return self if node.parent.nil?
  return self if @order[node.parent.priority, node.priority]

  node.remove_from_parents_list!
  @root = meld(node, @root)
  @root.parent = nil
  self
end
delete(elem) click to toggle source

Removes element from the heap

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

@raise [ArgumentError] if the element is not in the heap @return [self]

# File lib/pairing_heap.rb, line 208
def delete(elem)
  node = @nodes[elem]
  raise ArgumentError, "Provided element is not in heap" if node.nil?

  @nodes.delete(elem)
  if node.parent.nil?
    @root = merge_pairs(node.subheaps)
    if @root
      @root.parent = nil
      @root.prev_sibling = nil
      @root.next_sibling = nil
    end
  else
    node.remove_from_parents_list!
    new_heap = merge_pairs(node.subheaps)
    if new_heap
      @root = meld(new_heap, @root)
      @root.parent = nil
      @root.prev_sibling = nil
      @root.next_sibling = nil
    end
  end
  self
end
dequeue()
Alias for: pop
each() { |elem| ... } click to toggle source

Returns enumerator of elements. @note There are no order guarantees. @yieldparam [Object] element Element in the heap @return [Enumerator<Object>]

# File lib/pairing_heap.rb, line 265
def each
  return to_enum(__method__) { size } unless block_given?
  @nodes.each_value { |node| yield node.elem }
end
each_with_priority() { |elem, priority| ... } click to toggle source

Returns enumerator of elements. @note There are no order guarantees. @return [Enumerator<Array(Object, Object)>] if no block given @yieldparam [Array(Object, Object)] element Element in the heap with its priority

# File lib/pairing_heap.rb, line 274
def each_with_priority
  return to_enum(__method__) { size } unless block_given?
  @nodes.each_value { |node| yield [node.elem, node.priority] }
end
empty?() click to toggle source

Time Complexity: O(1) @return [Boolean]

# File lib/pairing_heap.rb, line 124
def empty?
  @root.nil?
end
enqueue(elem, priority = elem)
Alias for: push
exists?(key)
Alias for: include?
get_priority(elem) click to toggle source

Returns priority of the provided element

Time Complexity: O(1)

@return [Object] @return [nil] If element does not exist

# File lib/pairing_heap.rb, line 245
def get_priority(elem)
  node = @nodes[elem]
  node&.priority
end
get_priority_if_exists(elem) click to toggle source

Returns a pair where first element is success flag, and second element is priority

Time Complexity: O(1)

@return [Array(false, nil)] if the element is not in heap @return [Array(true, Object)] if the element is in heap;

second element of returned tuple is the priority
# File lib/pairing_heap.rb, line 255
def get_priority_if_exists(elem)
  node = @nodes[elem]
  return [false, nil] if node.nil?
  [true, node.priority]
end
include?(key) click to toggle source

Check if element is in the heap

Time Complexity: O(1)

@return [Boolean]

# File lib/pairing_heap.rb, line 236
def include?(key)
  @nodes.key?(key)
end
Also aliased as: exists?
length()
Alias for: size
offer(elem, priority = elem)
Alias for: push
peek() click to toggle source

Returns the element at the top of the heap

Time Complexity: O(1)

@return [Object] @return [nil] if the heap is empty

# File lib/pairing_heap.rb, line 106
def peek
  @root&.elem
end
peek_priority() click to toggle source

@return [Object] @return [nil] if the heap is empty

# File lib/pairing_heap.rb, line 112
def peek_priority
  @root&.priority
end
peek_with_priority() click to toggle source

@return [Array(Object, Object)] @return [Array(nil, nil)] if the heap is empty

# File lib/pairing_heap.rb, line 118
def peek_with_priority
  [@root&.elem, @root&.priority]
end
pop() click to toggle source

Removes element from the top of the heap and returns it

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

@return [Object] The top element @return [nil] If the heap is empty

# File lib/pairing_heap.rb, line 146
def pop
  return nil if @root.nil?

  elem = @root.elem
  @nodes.delete(elem)
  @root = merge_pairs(@root.subheaps)
  if @root
    @root.parent = nil
    @root.next_sibling = nil
    @root.prev_sibling = nil
  end
  elem
end
Also aliased as: dequeue
pop_priority() click to toggle source

@see pop @return [Object] @return [nil] if the heap is empty

# File lib/pairing_heap.rb, line 164
def pop_priority
  node = @root
  pop
  node&.priority
end
pop_with_priority() click to toggle source

@see pop @return [Array(Object, Object)] @return [Array(nil, nil)] If the heap is empty

# File lib/pairing_heap.rb, line 173
def pop_with_priority
  node = @root
  pop
  [node&.elem, node&.priority]
end
push(elem, priority = elem) click to toggle source

Pushes element to the heap.

Time Complexity: O(1)

@param elem Element to be pushed @param priority Priority of the element @raise [ArgumentError] if the element is already in the heap @return [self]

# File lib/pairing_heap.rb, line 87
def push(elem, priority = elem)
  raise ArgumentError, "Element already in the heap" if @nodes.key?(elem)

  node = Node.new(elem, priority)
  @nodes[elem] = node
  @root = if @root
    meld(@root, node)
  else
    node
  end
  self
end
Also aliased as: enqueue, offer
size() click to toggle source

Time Complexity: O(1) @return [Integer]

# File lib/pairing_heap.rb, line 136
def size
  @nodes.size
end
Also aliased as: length

Private Instance Methods

meld(left, right) click to toggle source
# File lib/pairing_heap.rb, line 283
def meld(left, right)
  if @order[left.priority, right.priority]
    parent = left
    child = right
  else
    parent = right
    child = left
  end
  child.next_sibling = parent.subheaps
  parent.subheaps = child
  child.next_sibling.prev_sibling = child if child.next_sibling
  child.prev_sibling = nil
  child.parent = parent
  parent
end