Class: PairingHeap::SimplePairingHeap

Inherits:
Object
  • Object
show all
Defined in:
lib/pairing_heap.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize {|l_priority, r_priority| ... } ⇒ SimplePairingHeap

Returns a new instance of SimplePairingHeap.

Yields:

  • (l_priority, r_priority) —

    Optional heap property priority comparator. ‘<:=.to_proc` by default

Yield Returns:

  • (boolean) —

    if ‘l_priority` is more prioritary than `r_priority`, or the priorities are equal



314
315
316
317
318
 
# File 'lib/pairing_heap.rb', line 314

def initialize(&block)
  @root = nil
  @order = block || :<=.to_proc
  @size = 0
end

Instance Attribute Details

#size ⇒ Integer (readonly) Also known as: length

Time Complexity: O(1)

Returns:

  • (Integer) 


372
373
374
 
# File 'lib/pairing_heap.rb', line 372

def size
  @size
end

Instance Method Details

#any? ⇒ Boolean

Time Complexity: O(1)

Returns:

  • (Boolean) 


366
367
368
 
# File 'lib/pairing_heap.rb', line 366

def any?
  !@root.nil?
end

#each {|element| ... } ⇒ Enumerator<Object>

Note:

There are no order guarantees.

Returns enumerator of elements.

Yield Parameters:

  • element (Object) —

    element in the heap

Returns:

  • (Enumerator<Object>) —

    if no block given



414
415
416
417
 
# 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 {|element| ... } ⇒ Enumerator<Array(Object, Object)>

Note:

There are no order guarantees.

Returns enumerator of elements.

Yield Parameters:

  • element (Array(Object, Object)) —

    Element in the heap with its priority

Returns:

  • (Enumerator<Array(Object, Object)>) —

    if no block given



423
424
425
426
 
# 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? ⇒ Boolean

Time Complexity: O(1)

Returns:

  • (Boolean) 


360
361
362
 
# File 'lib/pairing_heap.rb', line 360

def empty?
  @root.nil?
end

#merge(other) ⇒ self

Note:

This method modifies the argument

Merges provided heap

Time Complexity: O(1)

Parameters:

  • other —

    SimplePairingHeap to be merged

Returns:

  • (self)

Raises:

  • (ArgumentError) —

    if the provided argument is self



434
435
436
437
438
439
440
441
442
443
444
445
446
447
 
# File 'lib/pairing_heap.rb', line 434

def merge(other)
  if equal?(other)
    raise ArgumentError, "Cannot merge with itself"
  end
  other_root = other.root
  @root = if @root
    other_root ? meld(@root, other_root) : @root
  else
    other_root
  end
  @size += other.size
  other.clear!
  self
end

#peek ⇒ Object?

Returns the element at the top of the heap

Time Complexity: O(1)

Returns:

  • (Object)
  • (nil) —

    If the heap is empty



342
343
344
 
# File 'lib/pairing_heap.rb', line 342

def peek
  @root&.elem
end

#peek_priority ⇒ Object?

Returns:

  • (Object)
  • (nil) —

    If the heap is empty



348
349
350
 
# File 'lib/pairing_heap.rb', line 348

def peek_priority
  @root&.priority
end

#peek_with_priority ⇒ Array(Object, Object), Array(nil, nil)

Returns:

  • (Array(Object, Object))
  • (Array(nil, nil)) —

    If the heap is empty



354
355
356
 
# File 'lib/pairing_heap.rb', line 354

def peek_with_priority
  [@root&.elem, @root&.priority]
end

#pop ⇒ Object? Also known as: dequeue

Removes an element from the top of the heap and returns it

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

Returns:

  • (Object) —

    The top element

  • (nil) —

    If the heap is empty



380
381
382
383
384
385
386
387
388
389
 
# 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

#pop_priority ⇒ Object?

Returns:

  • (Object)
  • (nil) —

    If the heap is empty

See Also:



395
396
397
398
399
 
# File 'lib/pairing_heap.rb', line 395

def pop_priority
  node = @root
  pop
  node&.priority
end

#pop_with_priority ⇒ Array(Object, Object), Array(nil, nil)

Returns:

  • (Array(Object, Object))
  • (Array(nil, nil)) —

    If the heap is empty

See Also:



404
405
406
407
408
 
# File 'lib/pairing_heap.rb', line 404

def pop_with_priority
  node = @root
  pop
  [node&.elem, node&.priority]
end

#push(elem, priority = elem) ⇒ self Also known as: enqueue, offer

Pushes element to the heap.

Time Complexity: O(1)

Parameters:

  • elem —

    Element to be pushed

  • priority (defaults to: elem) —

    Priority of the element

Returns:

  • (self) 


325
326
327
328
329
330
331
332
333
334
 
# 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