util.queue

Interface SoftPriorityQueue<T>

Type Parameters:

T - the type of elements to be inserted into the soft priority queue

All Known Subinterfaces:

ExtendedPriorityQueue<T>, PriorityQueue<T>

All Known Implementing Classes:

BinaryHeap, FibonacciHeap, KAryHeap, SoftHeap

public interface SoftPriorityQueue<T>

A soft priority queue is a type of priority queue which is allowed to make mistakes. Unlike "normal" priority queues, soft priority queues may associate elements with a different key once they are inserted. Because of these so called corrupted elements, instead of extracting the minimal key, a different element may be returned

Method Summary

Modifier and Type	Method and Description
java.util.Collection<T>	corrupted() Returns a Collection of corrupted elements -- that is, elements which are associated with the wrong key.
default boolean	empty() Returns whether the queue is empty.
void	insert(T element) Inserts an element into the queue.
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.

Method Detail

peek

T peek()

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.

Returns:

the item with the minimal key

pop

T pop()

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.

Returns:

the item with the minimal key

corrupted

java.util.Collection<T> corrupted()

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

Returns:

a Collection of corrupted elements

insert

void insert(T element)

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

Parameters:

element - the element to be inserted

size

int size()

Returns the size of the queue.

Returns:

the size of the queue

empty

default boolean empty()

Returns whether the queue is empty.

Returns:

true if the queue is empty