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