class PairingHeap::SimplePairingHeap

Attributes

length[R]

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

size[R]

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

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 314
def initialize(&block)
  @root = nil
  @order = block || :<=.to_proc
  @size = 0
end

Public Instance Methods

any?() click to toggle source

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

# File lib/pairing_heap.rb, line 366
def any?
  !@root.nil?
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>] if no block given

# File lib/pairing_heap.rb, line 414
def each
  return to_enum(__method__) { size } unless block_given?
  NodeVisitor.visit_node(@root) { |x| yield x.elem }
end
each_with_priority() { |elem, priority| ... } click to toggle source

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

# File lib/pairing_heap.rb, line 423
def each_with_priority
  return to_enum(__method__) { size } unless block_given?
  NodeVisitor.visit_node(@root) { |x| yield [x.elem, x.priority] }
end
empty?() click to toggle source

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

# File lib/pairing_heap.rb, line 360
def empty?
  @root.nil?
end
enqueue(elem, priority = elem)
Alias for: push
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 342
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 348
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 354
def peek_with_priority
  [@root&.elem, @root&.priority]
end
pop() click to toggle source

Removes an 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 380
def pop
  return nil if @root.nil?
  @size -= 1

  elem = @root.elem
  @root = merge_pairs(@root.subheaps)
  @root&.next_sibling = nil

  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 395
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 404
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 @return [self]

# File lib/pairing_heap.rb, line 325
def push(elem, priority = elem)
  node = Node.new(elem, priority)
  @root = if @root
    meld(@root, node)
  else
    node
  end
  @size += 1
  self
end
Also aliased as: enqueue, offer

Private Instance Methods

meld(left, right) click to toggle source
# File lib/pairing_heap.rb, line 432
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
  parent
end