class BinaryHeap
An implementation of standard binary heap data structure. Internally, it uses an array as data store and a mutex for thread synchronization (insert and eject operations)
Public Class Methods
The constructor @param data [Array] the existent Array data on which the binary heap will be built @param block [Block] the comparator block, see examples.
default comparator is lambda {|parent, child| parent <=> child} which makes it a max binary heap.
@return [BinaryHeap] the Binary Heap instance @example A default max heap
bh = BinaryHeap.new
@example A min heap
bh = BinaryHeap.new{|parent, child| child <=> parent}
@example A max heap using self-defined comparator
bh = BinaryHeap.new{|parent, child| parent.bigger_or_equal_than(child)}
# File lib/binaryheap.rb, line 32 def initialize(data=nil, &block) @cmp = block || lambda{|parent, child| parent <=> child } @mutex = Mutex.new raise ParameterError.new("type of data must be Array or its subclass") unless data.nil? || data.is_a?(Array) @ary = data.nil? ? [] : build_from(data) end
Public Instance Methods
Adjust the heap to make it in good shape @param direction [Symbol] direction of adjustment, one of [:top_down, bottom_up] @return [BinaryHeap] the binay heap instance itself @note this method should be used carefully since it is not thread-safe, please check the implementation of BinaryHeap#eject
and BinaryHeap#insert
# File lib/binaryheap.rb, line 88 def adjust(direction = :top_down) return if @ary.size < 2 case direction when :top_down parent_idx = 0 until is_good?(parent_idx) child_idx = target_child_idx(parent_idx) swap(parent_idx, child_idx) parent_idx = child_idx end when :bottom_up child_idx = @ary.size - 1 parent_idx = p_idx(child_idx) until child_idx == 0 || @cmp.call(@ary[parent_idx], @ary[child_idx]) >= 0 swap(parent_idx, child_idx) child_idx = parent_idx parent_idx = p_idx(child_idx) end else raise ParameterError.new("invalid direction type") end self end
Return the underlying Aarray data
# File lib/binaryheap.rb, line 80 def data @ary end
Eject the top(max or min) element of the heap (heap will be adjusted automatically) @return [Object] the ejected element
# File lib/binaryheap.rb, line 55 def eject @mutex.synchronize do return nil if @ary.empty? e = @ary.first @ary[0] = @ary.last @ary.pop adjust(:top_down) e end end
Insert an element into the heap (heap will be adjusted automatically) @param element [Object] the element to be inserted into the heap @return [BinaryHeap] the binary heap instance itself
# File lib/binaryheap.rb, line 43 def insert(element) @mutex.synchronize do @ary.push(element) adjust(:bottom_up) end self end
Forward methods to underlying Array instance
# File lib/binaryheap.rb, line 113 def method_missing(name, *args, &blcok) @ary.send(name, *args, &blcok) end
Return the the top(max or min) element of the heap
# File lib/binaryheap.rb, line 67 def top @ary.first end
Set the top element of the heap @param element [Object] @note in most cases, this method should be used with the BinaryHeap#adjust
method @see BinaryHeap#adjust
# File lib/binaryheap.rb, line 75 def top=(element) @ary[0] = element end
Private Instance Methods
# File lib/binaryheap.rb, line 118 def build_from(data) heap = BinaryHeap.new(&(@cmp)) data.each{|e| heap.insert e} heap.data end
# File lib/binaryheap.rb, line 151 def is_good?(idx) if !lchid(idx).nil? return false unless @cmp.call(@ary[idx], lchid(idx)) >= 0 end if !rchild(idx).nil? return false unless @cmp.call(@ary[idx], rchild(idx)) >= 0 end true end
# File lib/binaryheap.rb, line 135 def l_idx(parent_idx) 2*parent_idx + 1 end
# File lib/binaryheap.rb, line 143 def lchid(parent_idx) @ary[l_idx(parent_idx)] end
# File lib/binaryheap.rb, line 130 def p_idx(child_idx) return nil if child_idx == 0 child_idx%2 == 0 ? (child_idx-2)/2 : child_idx/2 end
# File lib/binaryheap.rb, line 139 def r_idx(parent_idx) 2*parent_idx + 2 end
# File lib/binaryheap.rb, line 147 def rchild(parent_idx) @ary[r_idx(parent_idx)] end
# File lib/binaryheap.rb, line 124 def swap(i, j) temp = @ary[i] @ary[i] = @ary[j] @ary[j] = temp end
return the max/min child index
# File lib/binaryheap.rb, line 164 def target_child_idx(parent_idx) return nil if lchid(parent_idx).nil? && rchild(parent_idx).nil? l = lchid(parent_idx) r = rchild(parent_idx) l_idx = l_idx(parent_idx) r_idx = r_idx(parent_idx) return r_idx if l.nil? return l_idx if r.nil? return @cmp.call(l, r) >= 0 ? l_idx : r_idx end