module PairingHeap::MergePairs

Public Instance Methods

merge_pairs(heaps) click to toggle source

Non-recursive implementation of method described in en.wikipedia.org/wiki/Pairing_heap#delete-min

# 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