class BinaryHeap(T)

Included Modules

Defined in:

datastructure/binary_heap.cr

Constructors

Instance Method Summary

Instance methods inherited from module Enumerable(T)

accumulate(init : U) : Array(U) forall U
accumulate : Array(T)
accumulate(init : U, &block : U, T -> U) : Array(U) forall U
accumulate(&block : T, T -> T) : Array(T) accumulate, mex : T mex, mex_sorted : T mex_sorted, tally(*, default : Int32) : Hash(T, Int32) tally, unique : self
unique(&) : self unique

Constructor Detail

def self.new(enumerable : Enumerable(T)) #

Creates a new heap from the elements in enumerable.

a = BinaryHeap.new [3, 1, 2]
a.pop # => 1
a.pop # => 2
a.pop # => 3

[View source]
def self.new(initial_capacity : Int = 0) #

Creates a new empty heap backed by a buffer that is initially initial_capacity big (default: 0).

a = BinaryHeap.new(3)
a << 3 << 1 << 2
a.pop # => 1
a.pop # => 2
a.pop # => 3

[View source]
def self.new(enumerable : Enumerable(T), &block : T, T -> Int32?) #

Creates a new empty heap with the custom comperator.

The block must implement a comparison between two elements a and b, where a < b returns -1, a == b returns 0, and a > b returns 1. The comparison operator #<=> can be used for this.

a = BinaryHeap.new [3, 1, 2]
a.pop # => 1
b = BinaryHeap.new [3, 1, 2] { |a, b| b <=> a }
b.pop # => 3

[View source]
def self.new(initial_capacity : Int = 0, &block : T, T -> Int32?) #

Creates a new empty heap with the custom comperator.

The block must implement a comparison between two elements a and b, where a < b returns -1, a == b returns 0, and a > b returns 1. The comparison operator #<=> can be used for this.

a = BinaryHeap.new [3, 1, 2]
a.pop # => 1
b = BinaryHeap.new [3, 1, 2] { |a, b| b <=> a }
b.pop # => 3

[View source]

Instance Method Detail

def <<(object : T) : self #

Adds object to the heap and returns self.


[View source]
def ==(other : BinaryHeap(T)) : Bool #

Returns true if both heap have the same elements.


[View source]
def add(object : T) : self #

Adds object to the heap and returns self.


[View source]
def clear : self #

Removes all elements from the heap and returns self.


[View source]
def clone #

Returns a copy of self with all instance variables cloned.


[View source]
def each #

Returns an iterator for each element of the heap.


[View source]
def each(&) : Nil #

Yields each element of the heap, and returns nil.


[View source]
def empty? : Bool #

Returns true if self is empty, false otherwise.


[View source]
def inspect(io : IO) : Nil #

Writes a string representation of the heap to io.

BinaryHeap{1, 2}.inspect # => "BinaryHeap{1, 2}"

[View source]
def pop(n : Int) : Array(T) #

Removes the last n values from self ahd returns the removed values.


[View source]
def pop : T #

Removes the lowest value from self and returns the removed value. Raises IndexError if heap is of 0 size.


[View source]
def pop(&) #

Removes the lowest value from self and returns the removed value. If the array is empty, the given block is called.


[View source]
def pop? : T? #

Like #pop, but returns nil if self is empty.


[View source]
def size : Int32 #

Returns the number of elements in the heap.


[View source]
def sort : Array(T) #

Returns a new array with all elements sorted.

a = BinaryHeap.new [3, 1, 2]
a.sort # => [1, 2, 3]
b = BinaryHeap.new [3, 1, 2] { |a, b| b <=> a }
b.sort # => [3, 2, 1]

[View source]
def to_a : Array(T) #

Returns the elements as an Array.

BinaryHeap{3, 1, 2}.to_a # => [1, 3, 2]

[View source]
def to_s(io : IO) : Nil #

Writes a string representation of the heap to io.

BinaryHeap{1, 2}.to_s # => "BinaryHeap{1, 2}"

[View source]
def top : T #

Returns the lowest value in the self. If the self is empty, raises IndexError.


[View source]
def top(&) #

Returns the lowest value in the self. If the self is empty, calls the block and returns its value.


[View source]
def top? : T? #

Returns the lowest value in the self. If the self is empty, returns nil.


[View source]