class Algorithmable::DataStructs::Heap::Imp
Attributes
size[R]
Public Class Methods
new(collection = [], &block)
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 7 def initialize(collection = [], &block) @comparison_function = block || -> (this, other) { (this <=> other) < 0 } @queue = [] @size = 0 collection.each do |item| enqueue item end end
Public Instance Methods
dequeue()
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 27 def dequeue return if empty? maximum = @queue[1] exchange 1, @size @size = @size.pred sink 1 @queue[@size.next] = nil maintain_heap_invariant! maximum end
empty?()
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 16 def empty? !@size.nonzero? end
enqueue(key)
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 20 def enqueue(key) @size = @size.next @queue[@size] = key swim @size maintain_heap_invariant! end
peek()
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 38 def peek return if empty? @queue[1] end
Private Instance Methods
agreed(this, that)
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 71 def agreed(this, that) @comparison_function.call(@queue[this], @queue[that]) end
assert_heap_invariant(index)
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 55 def assert_heap_invariant(index) return true if index > @size left = 2 * index right = 2 * index + 1 return false if left <= @size && agreed(index, left) return false if right <= @size && agreed(index, right) assert_heap_invariant(left) && assert_heap_invariant(right) end
exchange(this, other)
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 45 def exchange(this, other) swap = @queue[this] @queue[this] = @queue[other] @queue[other] = swap end
maintain_heap_invariant!()
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 51 def maintain_heap_invariant! fail "Heap is not invariant now: #{inspect}!" unless assert_heap_invariant(1) end
sink(index)
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 75 def sink(index) while 2 * index <= @size temp_index = 2 * index temp_index = temp_index.next if temp_index < @size && agreed(temp_index, temp_index.next) break unless agreed(index, temp_index) exchange(index, temp_index) index = temp_index end end
swim(index)
click to toggle source
# File lib/algorithmable/data_structs/heap/imp.rb, line 64 def swim(index) while index > 1 && agreed(index / 2, index) exchange(index, index / 2) index /= 2 end end