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