class Rx::Util::Heap

Attributes

comparator[R]
heap[R]

Public Class Methods

new(items = [], &comparator) click to toggle source
# File lib/rx/util/heap.rb, line 37
def initialize(items = [], &comparator)
  @heap = items.dup
  @comparator = block_given? ? comparator : -> (a, b) { a < b }
  sort!
end

Public Instance Methods

<<(item) click to toggle source
# File lib/rx/util/heap.rb, line 43
def <<(item)
  push(item)
end
peek() click to toggle source
# File lib/rx/util/heap.rb, line 47
def peek
  heap.first
end
pop() click to toggle source
# File lib/rx/util/heap.rb, line 51
def pop
  item = heap.shift
  sort!
  item
end
push(item) click to toggle source
# File lib/rx/util/heap.rb, line 57
def push(item)
  heap << item
  sort!
  self
end

Private Instance Methods

left(n) click to toggle source
# File lib/rx/util/heap.rb, line 67
def left(n)
  2 * n + 1
end
parent(n) click to toggle source
# File lib/rx/util/heap.rb, line 71
def parent(n)
  (n - 1) / 2
end
right(n) click to toggle source
# File lib/rx/util/heap.rb, line 75
def right(n)
  2 * n + 2
end
sort!() click to toggle source
# File lib/rx/util/heap.rb, line 79
def sort!
  return if heap.length <= 1
  n = parent(heap.length - 1)
  while n >= 0
    l = left(n)
    r = right(n)
    s = n

    if comparator.call(heap[l], heap[s])
      s = l
    end

    if r < heap.length && comparator.call(heap[r], heap[s])
      s = r
    end

    if s != n
      heap[s], heap[n] = heap[n], heap[s]
    end

    n -= 1
  end
end