class SkewHeap

A dynamic priority queue. Implements standard push, pop, and peek operations and allows efficient merging of two +SkewHeap+s

Author: Paul J Sanchez (pjs@alum.mit.edu)
Copyright: Copyright © Paul J Sanchez
License: LGPL

Constants

Node: Classic tree node with a data payload and left and right references.

Attributes

root[R]

Public Class Methods

new(ary=[], &block) click to toggle source

Construct and initialize a new SkewHeap. If a comparator block is provided it will be used to determine ordering for the data, otherwise the default ordering will be used.

Arguments

ary -> an optional array of data to add to the new SkewHeap.

# File lib/skewheap.rb, line 20
def initialize(ary=[], &block)
  @cmp_fn = block || lambda {|x,y| x <=> y}
  @root = nil
  ary.each {|item| push(item)} unless ary.empty?
end

Public Instance Methods

clear() click to toggle source

Remove all elements from the SkewHeap.

# File lib/skewheap.rb, line 51
def clear
  @root = nil
end

empty?() click to toggle source

Test whether or not the SkewHeap is empty.

# File lib/skewheap.rb, line 46
def empty?
  @root.nil?
end

join(other)

Alias for: merge

merge(other) click to toggle source

Combine two Skewheaps.

Arguments

other -> the other SkewHeap to merge into this one.

Returns

a reference to the combined SkewHeap.

Raises

RuntimeError if other is not a SkewHeap

# File lib/skewheap.rb, line 64
def merge(other)
  if other.kind_of? SkewHeap
    @root = __merge__(@root, other.root)
    self
  else
    raise "Attempt to merge a non-SkewHeap with a SkewHeap."
  end
end

Also aliased as: join

peek() click to toggle source

View the first element in the SkewHeap without removing it.

# File lib/skewheap.rb, line 41
def peek
  @root.payload if @root
end

pop() click to toggle source

Remove and return the first element in the SkewHeap.

# File lib/skewheap.rb, line 32
def pop
  if @root
    return_value = @root.payload
    @root = __merge__(@root.left, @root.right)
    return_value
  end
end

push(item) click to toggle source

Add the provided item to the SkewHeap.

# File lib/skewheap.rb, line 27
def push(item)
  @root = __merge__(@root, Node.new(item)) unless item.nil?
end

Private Instance Methods

__merge__(h1, h2) click to toggle source

# File lib/skewheap.rb, line 80
def __merge__(h1, h2)
  return h2 if h1.nil?
  return h1 if h2.nil?
  if @cmp_fn[h1.payload, h2.payload] < 1
    h1.right, h1.left = h1.left, __merge__(h1.right, h2)
    return h1
  else
    h2.right, h2.left = h2.left, __merge__(h2.right, h1)
    return h2
  end
end