class Algorithmix::DataStructure::Heap::BinaryHeap
Public Class Methods
Creates a new binary heap.
@param obj [#to_a] can be any object, which responds to to_a
method. By default is set to nil. @kwarg copy [true, false] if is set to true, content of the object will be copied into content of the new heap.
By default is set to false.
@kwarg min [true, false] defines the type of the new heap, be default min is set to false @raise ArgumentError, if given object doesn't respond to to_a
method. @return [BinaryHeap] a newly created binary heap
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 17 def initialize(obj = nil, copy: false, min: false) @container = [] @max = min ? false : true obj.nil? ? nil : from_obj(obj, copy) end
Public Instance Methods
Compares contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap. @return [true, false] false if heaps are equal, true otherwise
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 147 def !=(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#!= for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) @container != binary_heap.to_a end
Finds the intersection of contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] a new binary heap
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 245 def &(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#& for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) BinaryHeap.new(@container & binary_heap.to_a, min: !@max) end
Concatenates contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] a new binary heap
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 176 def +(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#+ for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) BinaryHeap.new(@container + binary_heap.to_a, min: !@max) end
Finds the difference of contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] a new binary heap
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 271 def -(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#- for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) BinaryHeap.new(@container - binary_heap.to_a, min: !@max) end
(see insert
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 45 def <<(value) insert(value) end
Compares contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap. @return
> 1 if content of the heap is greater than content of the given heap¶ ↑
> 0 if contents are equal¶ ↑
> -1 if content of the given heap is greater than content of the heap¶ ↑
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 166 def <=>(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#<=> for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) @container <=> binary_heap.to_a end
Compares contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap. @return [true, false] true if heaps are equal, false otherwise
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 131 def ==(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#== for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) @container == binary_heap.to_a end
Finds the symmetric difference of contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] a new binary heap
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 297 def ^(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#^ for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) result = (@container | binary_heap.to_a) - (@container & binary_heap.to_a) BinaryHeap.new(result, min: !@max) end
(see map
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 384 def apply(&block) map(&block) end
(see map!
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 389 def apply!(&block) map!(&block) end
Assigns content of an object, to content of the heap.
@param obj [#to_a] can be any object, which responds to to_a
method. By default is set to nil. @kwarg copy [true, false] if is set to true, content of the object will be copied into content of the new heap.
By default is set to false.
@raise ArgumentError, if given object doesn't respond to to_a
method. @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 30 def assign(obj, copy: false) from_obj(obj, copy) end
Clears content of the heap.
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 326 def clear @container = [] self end
(see +
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 183 def concat(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#concat for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) self + binary_heap end
Concatenates contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 199 def concat!(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#concat! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) from_obj(@container + binary_heap.to_a, false) end
Decreases a value in the heap, if current heap is set to be min heap.
@kwarg idx [Integer] any integer, which can represent index at an array. @krarg old_value @kwarg new_value @raise TypeError, if current heap has type max heap @raise ArgumentError, if idx or old_value are not provided @raise ArgumentError, if new_value is not provided @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 114 def decrease_key(idx: nil, old_value: nil, new_value: nil) raise TypeError, "Undefined method BinaryHeap#decrease_key for MaxBinaryHeap" if @max raise ArgumentError, "At least one of both options must be provided." if idx.nil? && old_value.nil? raise ArgumentError, ":new_value cannot be nil." if new_value.nil? idx = idx.nil? && !old_value.nil? ? @container.index(old_value) : idx raise ArgumentError, "Element at position #{idx} doesn't exist." if idx.nil? || @container[idx].nil? change_key(idx, new_value) self end
(see #!=)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 153 def diff?(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#diff? for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) self != binary_heap end
(see -
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 277 def difference(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#difference for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) self - binary_heap end
Finds the difference of contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 287 def difference!(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#difference! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) from_obj(@container - binary_heap.to_a, false) end
Returns information for current …
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 79 def empty? @container.empty? end
(see #==)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 137 def eql?(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#eql? for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) self == binary_heap end
Removes top element of the heap.
@raise Algorithmix::EmptyContainerError, if the heap is empty. @return top element of the heap.
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 53 def extract raise EmptyContainerError, "The Binary heap is empty." if @container.empty? @container[0], @container[@container.length - 1] = @container[@container.length - 1], @container[0] value = @container.pop heapify(0) value end
(see select
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 348 def filter(&block) select(&block) end
(see select!
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 353 def filter!(&block) select!(&block) end
(see select
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 358 def find_all(&block) select(&block) end
(see select!
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 363 def find_all!(&block) select!(&block) end
Increases a value in the heap, if current heap is set to be max heap.
@kwarg idx [Integer] any integer, which can represent index at an array. @krarg old_value @kwarg new_value @raise TypeError, if current heap has type min heap @raise ArgumentError, if idx or old_value are not provided @raise ArgumentError, if new_value is not provided @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 92 def increase_key(idx: nil, old_value: nil, new_value: nil) raise TypeError, "Undefined method BinaryHeap#increase_key for MinBinaryHeap" if !@max raise ArgumentError, "At least one of both options must be provided." if idx.nil? && old_value.nil? raise ArgumentError, ":new_value cannot be nil." if new_value.nil? idx = idx.nil? && !old_value.nil? ? @container.index(old_value) : idx raise ArgumentError, "Element at position #{idx} doesn't exist." if idx.nil? || @container[idx].nil? change_key(idx, new_value, increase: true) self end
Inserts a value in the heap.
@param value @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 38 def insert(value) @container << value sift_up(@container.size - 1) self end
(see #&)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 251 def intersect(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#intersect for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) self & binary_heap.to_a end
Finds the intersection of contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 261 def intersect!(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#intersect! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) from_obj(@container & binary_heap.to_a, false) end
(see size
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 74 def length @container.size end
Applies a function to each element of the heap.
@param block @return [BinaryHeap] a new binary heap
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 371 def map(&block) BinaryHeap.new(@container.map { |e| block.call(e)}, min: !@max) end
Applies a function to each element of the heap.
@param block @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 379 def map!(&block) from_obj(@container.map { |e| block.call(e)}, false) end
(see +
)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 189 def merge(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#merge for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) self + binary_heap end
Concatenates contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 209 def merge!(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#merge! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) from_obj(@container + binary_heap.to_a, false) end
Filters elements of the heap by given condition.
@param block @return [BinaryHeap] a new binary heap
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 335 def select(&block) BinaryHeap.new(@container.select { |e| block.call(e)}, min: !@max) end
Filters elements of the heap by given condition.
@param block @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 343 def select!(&block) from_obj(@container.select { |e| block.call(e)}, false) end
Returns number of elements in the heap.
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 69 def size @container.size end
(see #^)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 304 def symmetric_difference(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#symmetric_difference for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) self ^ binary_heap end
Finds the symmetric difference of contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 314 def symmetric_difference!(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#symmetric_difference! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) result = (@container | binary_heap.to_a) - (@container & binary_heap.to_a) from_obj(result, false) end
Converts content of the heap to an array.
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 321 def to_a @container end
Returns top element of the heap, without removing it.
@return top element.
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 64 def top @container.first end
(see #|)
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 225 def union(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#union for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) self | binary_heap end
Unites contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] self object
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 235 def union!(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#union! for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) from_obj(@container | binary_heap.to_a, false) end
Unites contents of the heap, and a heap given as argument.
@param binary_heap [BinaryHeap] @raise ArgumentError, if given object is not a heap @return [BinaryHeap] a new binary heap
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 219 def |(binary_heap) raise ArgumentError, "Undefined method BinaryHeap#| for #{binary_heap}:#{binary_heap.class}" unless binary_heap.is_a?(BinaryHeap) BinaryHeap.new(@container | binary_heap.to_a, min: !@max) end
Private Instance Methods
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 429 def build_heap (@container.length / 2).downto(0) do |idx| heapify(idx) end end
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 446 def change_key(idx, value, increase: false) idx = idx < 0 ? idx + @container.size : idx @container[idx] = increase ? (@container[idx] < value ? value : @container[idx]) : (@container[idx] > value ? value : @container[idx]) sift_up(idx) end
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 395 def from_obj(obj, copy) raise ArgumentError, "Object doesn't respond to #to_a method" unless obj.respond_to?(:to_a) @container = copy ? obj.send(:to_a).dup : obj.send(:to_a) build_heap self end
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 403 def heapify(idx) return if idx.nil? lhs = idx * 2 + 1 rhs = idx * 2 + 2 current = idx if !@container[lhs].nil? && ((@max && @container[lhs] > @container[current]) || (!@max && @container[lhs] < @container[current])) current = lhs end if !@container[rhs].nil? && ((@max && @container[rhs] > @container[current]) || (!@max && @container[rhs] < @container[current])) current = rhs end if current != idx @container[idx], @container[current] = @container[current], @container[idx] heapify(current) end end
# File lib/algorithmix/data_structure/heap/binary_heap.rb, line 435 def sift_up(idx) return if idx.zero? parent = idx.even? ? idx / 2 - 1 : idx / 2 if (@max && @container[parent] < @container[idx]) || (!@max && @container[parent] > @container[idx]) @container[parent], @container[idx] = @container[idx], @container[parent] sift_up(parent) end end