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
Public Class Methods
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 newSkewHeap
.
-
# 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
Remove all elements from the SkewHeap
.
# File lib/skewheap.rb, line 51 def clear @root = nil end
Test whether or not the SkewHeap
is empty.
# File lib/skewheap.rb, line 46 def empty? @root.nil? end
Combine two Skewheaps.
- Arguments
-
other
-> the otherSkewHeap
to merge into this one.
-
- Returns
-
a reference to the combined
SkewHeap
.
-
- Raises
-
RuntimeError if
other
is not aSkewHeap
-
# 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
View the first element in the SkewHeap
without removing it.
# File lib/skewheap.rb, line 41 def peek @root.payload if @root end
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
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
# 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