class PulsarSdk::Tweaks::BinaryHeap
Attributes
data[R]
Public Class Methods
new(ary=nil, &block)
click to toggle source
default is max heap, custom compare lambda to build your sort
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 7 def initialize(ary=nil, &block) @cmp = block || lambda{|parent, child| parent <=> child } @mutex = Mutex.new raise "type of ary must be Array or its subclass" unless ary.nil? || ary.is_a?(Array) @data = build_from(ary) end
Public Instance Methods
insert(*elements)
click to toggle source
insert an element list into heap, it will automatic adjust
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 16 def insert(*elements) @mutex.synchronize do elements.each do |x| data.push(x) adjust(:bottom_up) end end end
shift()
click to toggle source
take the heap element and adjust heap
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 26 def shift @mutex.synchronize do return if data.empty? e = data.first data[0] = data.last data.pop adjust(:top_down) e end end
top()
click to toggle source
return the the top element of the heap
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 38 def top data.first end
Private Instance Methods
adjust(direction = :top_down)
click to toggle source
make the heap in good shape
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 93 def adjust(direction = :top_down) return if data.size < 2 case direction when :top_down parent_idx = 0 until good?(parent_idx) child_idx = find_child_idx(parent_idx) swap(parent_idx, child_idx) parent_idx = child_idx end when :bottom_up child_idx = data.size - 1 parent_idx = p_idx(child_idx) until child_idx == 0 || compare(parent_idx, child_idx) swap(parent_idx, child_idx) child_idx = parent_idx parent_idx = p_idx(child_idx) end else raise "invalid direction type" end end
build_from(ary)
click to toggle source
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 43 def build_from(ary) return [] if ary.nil? || ary.empty? heap = BinaryHeap.new(&(@cmp)) heap.insert(*ary) heap.data end
compare(i, j)
click to toggle source
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 55 def compare(i, j) @cmp.call(data[i], data[j]) >= 0 end
find_child_idx(parent_idx)
click to toggle source
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 117 def find_child_idx(parent_idx) l = lchid(parent_idx) r = rchild(parent_idx) return if l.nil? && r.nil? l_idx_ = l_idx(parent_idx) r_idx_ = r_idx(parent_idx) return r_idx_ if l.nil? return l_idx_ if r.nil? compare(l_idx_, r_idx_) ? l_idx_ : r_idx_ end
good?(idx)
click to toggle source
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 80 def good?(idx) if !lchid(idx).nil? return false unless compare(idx, l_idx(idx)) end if !rchild(idx).nil? return false unless compare(idx, r_idx(idx)) end true end
l_idx(parent_idx)
click to toggle source
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 64 def l_idx(parent_idx) (parent_idx << 1) + 1 end
lchid(parent_idx)
click to toggle source
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 72 def lchid(parent_idx) data[l_idx(parent_idx)] end
p_idx(child_idx)
click to toggle source
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 59 def p_idx(child_idx) return nil if child_idx == 0 child_idx%2 == 0 ? (child_idx-2)/2 : child_idx/2 end
r_idx(parent_idx)
click to toggle source
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 68 def r_idx(parent_idx) (parent_idx << 1) + 2 end
rchild(parent_idx)
click to toggle source
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 76 def rchild(parent_idx) data[r_idx(parent_idx)] end
swap(i, j)
click to toggle source
# File lib/pulsar_sdk/tweaks/binary_heap.rb, line 51 def swap(i, j) data[i], data[j] = data[j], data[i] end