class CGL::BinaryHeap(T)

CGL::BinaryHeap(T)
Reference
Object

Overview

A simple priority queue implemented as a array-based heap.

Each inserted elements is given a certain priority, based on the result of the comparison. This is a min-heap, which means retrieving an element will always return the one with the highest priority.

To avoid O(n) complexity when deleting an arbitrary element, a map is used to cache indices for each element.

Defined in:

cgl/utils/binary_heap.cr

Constructors

.new(initial_capacity : Int)
.new
Creates a new empty BinaryHeap.

Instance Method Summary

#==(other : BinaryHeap) : Bool
#==(other) : Bool
Returns false (other can only be a Value here).
#adjust(value : T, with new_priority : Number)
#clear
#delete(value : T) : T?
#empty? : Bool
#heapify!
#includes?(value : T) : Bool
#inspect(io)
#next_priority : Float64
#next_priority(&)
#peek : T
#peek(&)
#peek? : T?
#pop : T
#push(priority : Number, value : T) : self
#size : Int32
Returns the number of elements in the heap.
#to_a : Array(Tuple(Float64, T))
#to_slice : Slice(Tuple(Float64, T))

Constructor Detail

def self.new(initial_capacity : Int) #

def self.new #

Creates a new empty BinaryHeap.

Instance Method Detail

def ==(other : BinaryHeap) : Bool #

def ==(other) : Bool #

Description copied from class Reference

Returns false (other can only be a Value here).

def adjust(value : T, with new_priority : Number) #

def clear #

def delete(value : T) : T? #

def empty? : Bool #

def heapify! #

def includes?(value : T) : Bool #

def inspect(io) #

def next_priority : Float64 #

def next_priority(&) #

def peek : T #

def peek(&) #

def peek? : T? #

def pop : T #

def push(priority : Number, value : T) : self #

def size : Int32 #

Returns the number of elements in the heap.

def to_a : Array(Tuple(Float64, T)) #

def to_slice : Slice(Tuple(Float64, T)) #