class PairingHeap::PairingHeap
Pairing heap data structure implementation @see en.wikipedia.org/wiki/Pairing_heap
Public Class Methods
@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
Time Complexity: O(1) @return [Boolean]
# File lib/pairing_heap.rb, line 130 def any? !@root.nil? end
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
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
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
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
Time Complexity: O(1) @return [Boolean]
# File lib/pairing_heap.rb, line 124 def empty? @root.nil? end
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
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
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
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
@return [Object] @return [nil] if the heap is empty
# File lib/pairing_heap.rb, line 112 def peek_priority @root&.priority end
@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
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
@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
@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
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
Time Complexity: O(1) @return [Integer]
# File lib/pairing_heap.rb, line 136 def size @nodes.size end
Private Instance Methods
# 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