module PairingHeap::MergePairs
Public Instance Methods
Source
# File lib/pairing_heap.rb, line 6 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] pairs = nil left = heaps while left right = left.next_sibling unless right left.next_sibling = pairs pairs = left break end next_val = right.next_sibling right = meld(left, right) right.next_sibling = pairs pairs = right left = next_val end # [H1H2, H3H4, H5H6, H7] # [H1H2, H3H4, H5H67] # [H1H2, H3H45H67] # [H1H2H3H45H67] # return H1H2H3H45H67 left = pairs right = pairs.next_sibling while right next_val = right.next_sibling left = meld(left, right) right = next_val end left end
Non-recursive implementation of method described in en.wikipedia.org/wiki/Pairing_heap#delete-min