util.queue

Class SoftHeap<T>

java.lang.Object

util.queue.SoftHeap<T>

Type Parameters:

T - the type of element to be stored in the soft heap

All Implemented Interfaces:

Meldable<SoftHeap<T>>, SoftPriorityQueue<T>

public class SoftHeap<T>
extends java.lang.Object
implements SoftPriorityQueue<T>, Meldable<SoftHeap<T>>

The soft heap, first described by Chazelle, is an approximate data structure similar to a priority queue. It achieves a constant runtime on all operations but insert. The runtime of insert is in O(log(1/e)), where e is the error rate of the soft heap.
Soft heaps achieve this runtime by grouping elements together and associating all elements in the same group with the same key. Thus, the depth of the binary heaps that build the core of this data structure is drastically reduced. This grouping of elements leads to a loss of precision.
This class doesn't contain an implementation of the soft heap as Chazelle devised it, but an easier version described by Kaplan and Zwick

See Also:

SoftPriorityQueue

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
protected class	SoftHeap.BinaryHeap Represents a binary heap in the queue of binary heaps that the soft heap consists of
protected class	SoftHeap.BinaryHeapNode

Constructor Summary

Constructors

Constructor and Description
SoftHeap(double errorRate, java.util.Comparator<? super T> comparator) Constructs an empty soft heap with the given error rate.
SoftHeap(double errorRate, java.util.Comparator<? super T> comparator, T element) Constructs a new soft heap with the given error rate containing the specified element.

Method Summary

Modifier and Type	Method and Description
void	clear() Resets the binary heap
java.util.Collection<T>	corrupted() Returns a Collection of corrupted elements -- that is, elements which are associated with the wrong key.
void	insert(T element) Inserts an element into the queue.
void	meld(SoftHeap<T> other) Destructively melds other into this.
static <S extends java.lang.Comparable<? super S>> SoftHeap<S>	naturallyOrdered(double errorRate) Creates a new soft heap on the basis of the comparable type argument and the given error rate.
T	peek() Peeks into the top of the queue, returning the element which is believed to have minimal key.
T	pop() Peeks into the top of the queue, returning the element which is believed to have minimal key.
int	size() Returns the size of the queue.
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface util.queue.SoftPriorityQueue

empty

Constructor Detail

SoftHeap

public SoftHeap(double errorRate,
                java.util.Comparator<? super T> comparator,
                T element)

Constructs a new soft heap with the given error rate containing the specified element.

Parameters:

errorRate - the error rate of the soft heap

comparator - used to compare the elements of the soft heap. If T implements Comparable, you might also use naturallyOrdered(double)

element - the element that the SoftHeap should be initialized with

SoftHeap

public SoftHeap(double errorRate,
                java.util.Comparator<? super T> comparator)

Constructs an empty soft heap with the given error rate.

Parameters:

errorRate - the error rate of the soft heap

comparator - used to compare the elements of the soft heap. If T implements Comparable, you might also use naturallyOrdered(double)

Method Detail

naturallyOrdered

public static <S extends java.lang.Comparable<? super S>> SoftHeap<S> naturallyOrdered(double errorRate)

Creates a new soft heap on the basis of the comparable type argument and the given error rate.

Type Parameters:

S - the type of element to be stored in the soft heap

Parameters:

errorRate - the error rate of the soft heap

Returns:

an empty soft heap with the given error rate

size

public int size()

Description copied from interface: SoftPriorityQueue

Returns the size of the queue.

Specified by:

size in interface SoftPriorityQueue<T>

Returns:

the size of the queue

corrupted

public java.util.Collection<T> corrupted()

Description copied from interface: SoftPriorityQueue

Returns a Collection of corrupted elements -- that is, elements which are associated with the wrong key.

Specified by:

corrupted in interface SoftPriorityQueue<T>

Returns:

a Collection of corrupted elements

peek

public T peek()

Description copied from interface: SoftPriorityQueue

Peeks into the top of the queue, returning the element which is believed to have minimal key. Does not remove the item from the queue.

Specified by:

peek in interface SoftPriorityQueue<T>

Returns:

the item with the minimal key

pop

public T pop()

Description copied from interface: SoftPriorityQueue

Peeks into the top of the queue, returning the element which is believed to have minimal key. The item will get removed from the queue in the process.

Specified by:

pop in interface SoftPriorityQueue<T>

Returns:

the item with the minimal key

insert

public void insert(T element)

Description copied from interface: SoftPriorityQueue

Inserts an element into the queue. The item or other items may be corrupted in the process.

Specified by:

insert in interface SoftPriorityQueue<T>

Parameters:

element - the element to be inserted

clear

public void clear()

Resets the binary heap

meld

public void meld(SoftHeap<T> other)

Description copied from interface: Meldable

Destructively melds other into this.

Specified by:

meld in interface Meldable<SoftHeap<T>>

Parameters:

other - the element to meld into this

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object