class PairingHeap::PairingHeap

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

Public Class Methods

new(&block) click to toggle source

@param &block Optional heap property priority comparator. `<:=.to_proc` by default

# File lib/pairing_heap.rb, line 21
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 57
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 heap is not in heap or the new priority is less prioritary @return [PairingHeap]

# File lib/pairing_heap.rb, line 95
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 if node.parent.nil?
  return if @order[node.parent.priority, node.priority]

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

Removes element from the top of the heap

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

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

# File lib/pairing_heap.rb, line 117
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)
  else
    remove_from_parents_list(node)
    new_heap = merge_pairs(node.subheaps)
    if new_heap
      new_heap.prev_sibling = nil
      new_heap.next_sibling = nil
    end
    @root = meld(new_heap, @root)
  end
  @root&.parent = nil
  self
end
dequeue()
Alias for: pop
empty?() click to toggle source

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

# File lib/pairing_heap.rb, line 51
def empty?
  @root.nil?
end
enqueue(elem, priority)
Alias for: push
length()
Alias for: size
peek() click to toggle source

Returns the element at the top of the heap

Time Complexity: O(1)
# File lib/pairing_heap.rb, line 45
def peek
  @root&.elem
end
pop() click to toggle source

Removes element from the top of the heap

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

@raise [ArgumEntError] if the heap is empty @return [PairingHeap]

# File lib/pairing_heap.rb, line 73
def pop
  raise ArgumentError, "Cannot remove from an empty heap" 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
push(elem, priority) 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 [PairingHeap]

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

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

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

# File lib/pairing_heap.rb, line 63
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 153
def meld(left, right)
  return right if left.nil?
  return left if right.nil?

  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
merge_pairs(heaps) click to toggle source

Non-recursive implementation of method described in en.wikipedia.org/wiki/Pairing_heap#delete-min

# File lib/pairing_heap.rb, line 173
def merge_pairs(heaps)
  return nil if heaps.nil?
  return heaps if heaps.next_sibling.nil?

  # [H1, H2, H3, H4, H5, H6, H7] => [H1H2, H3H4, H5H6, H7]
  stack = []
  current = heaps
  while current
    prev = current
    current = current.next_sibling
    unless current
      stack << prev
      break
    end
    next_val = current.next_sibling
    stack << meld(prev, current)
    current = next_val
  end

  # [H1H2, H3H4, H5H6, H7]
  # [H1H2, H3H4, H5H67]
  # [H1H2, H3H45H67]
  # [H1H2H3H45H67]
  # return H1H2H3H45H67
  while true
    right = stack.pop
    return right if stack.empty?

    left = stack.pop
    stack << meld(left, right)
  end
end
remove_from_parents_list(node) click to toggle source
# File lib/pairing_heap.rb, line 139
def remove_from_parents_list(node)
  if node.prev_sibling
    node.prev_sibling.next_sibling = node.next_sibling
    node.next_sibling.prev_sibling = node.prev_sibling if node.next_sibling
  elsif node.parent.subheaps.equal?(node)
    node.parent.subheaps = node.next_sibling
    node.next_sibling.prev_sibling = nil if node.next_sibling
  elsif node.next_sibling
    node.next_sibling.prev_sibling = nil
  end
  node.prev_sibling = nil
  node.next_sibling = nil
end