class Crystalg::DataStructures::RandomizedMeldableHeap(T)

Overview

A randomized meldable heap is a priority queue allowed merging heaps by supporting internal method called meld.

Defined in:

crystalg/data_structures/randomized_meldable_heap.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new(order : Symbol = :min, seed : UInt64 = 123456789) #

Creates a new RandomizedMeldableHeap(T). The order parameter must be :min or :max.


[View source]

Instance Method Detail

def absorb(other : RandomizedMeldableHeap(T)) #

Adds all elements of the meldable heap Q passed as parameter to this heap, and then emptying Q. O(log n).

heap1 = RandomizedMeldableHeap(Int32).new
heap2 = RandomizedMeldableHeap(Int32).new
[1, 2, 3].each { |e| heap1.push(e) }
[4, 5, 6].each { |e| heap2.push(e) }

heap1.absorb(heap2)

heap2.top # => nil

heap1.top     # => 1
heap1.pop.top # => 2
heap1.pop.top # => 3
heap1.pop.top # => 4
heap1.pop.top # => 5
heap1.pop.top # => 6
heap1.pop.top # => nil

[View source]
def pop #

Pops the highest priority value from heap. O(log n).

heap = RandomizedMeldableHeap(Int32).new

heap.push(3).push(2).push(1)
heap.pop
heap.top # => 2

[View source]
def push(value : T) #

Pushes a new value to heap. O(log n)

heap = RandomizedMeldableHeap(Int32).new
heap.push(2)
heap.top # => 2

[View source]
def remove(value) #

Removes all values equal a parameter from heap. O(k log n). k is number of removed elements.

heap = RandomizedMeldableHeap(Int32).new

[10, 1, 2, 2, 2, 11, 2].each { |e| heap.push(e) }

heap.remove(2)

heap.top # => 1
heap.pop.top # => 10
heap.pop.top # => 11
heap.pop.top # => nil

[View source]
def size #

Returns number of elements in a heap. 0 if a heap is empty. O(1).

heap = RandomizedMeldableHeap(Int32).new

heap.size # => 0
heap.push(1).size # => 1

[View source]
def top #

Returns the higheset priority value or nil if heap is empty. O(1).

heap = RandomizedMeldableHeap(Int32).new

heap.top # => nil
heap.push(1).top # => 1

[View source]