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