class PairingHeap::SimplePairingHeap
Attributes
Time Complexity: O(1) @return [Integer]
Time Complexity: O(1) @return [Integer]
Public Class Methods
Source
# File lib/pairing_heap.rb, line 314 def initialize(&block) @root = nil @order = block || :<=.to_proc @size = 0 end
@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
Public Instance Methods
Source
# File lib/pairing_heap.rb, line 366 def any? !@root.nil? end
Time Complexity: O(1) @return [Boolean]
Source
# 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
Returns enumerator of elements. @note There are no order guarantees. @yieldparam [Object] element element in the heap @return [Enumerator<Object>] if no block given
Source
# 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
@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.
Source
# File lib/pairing_heap.rb, line 360 def empty? @root.nil? end
Time Complexity: O(1) @return [Boolean]
Source
# 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
Merges provided heap
Time Complexity: O(1)
@param other SimplePairingHeap
to be merged @return [self] @raise [ArgumentError] if the provided argument is self @note This method modifies the argument
Source
# File lib/pairing_heap.rb, line 342 def peek @root&.elem end
Returns the element at the top of the heap
Time Complexity: O(1)
@return [Object] @return [nil] If the heap is empty
Source
# File lib/pairing_heap.rb, line 348 def peek_priority @root&.priority end
@return [Object] @return [nil] If the heap is empty
Source
# File lib/pairing_heap.rb, line 354 def peek_with_priority [@root&.elem, @root&.priority] end
@return [Array(Object, Object)] @return [Array(nil, nil)] If the heap is empty
Source
# 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
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
Source
# File lib/pairing_heap.rb, line 395 def pop_priority node = @root pop node&.priority end
@see pop
@return [Object] @return [nil] If the heap is empty
Source
# File lib/pairing_heap.rb, line 404 def pop_with_priority node = @root pop [node&.elem, node&.priority] end
@see pop
@return [Array(Object, Object)] @return [Array(nil, nil)] If the heap is empty
Source
# 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
Pushes element to the heap.
Time Complexity: O(1)
@param elem Element to be pushed @param priority Priority of the element @return [self]
Protected Instance Methods
Private Instance Methods
Source
# File lib/pairing_heap.rb, line 453 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