org.key_project.util.collection

Class ImmutableLeftistHeap.Node<S extends java.lang.Comparable<S>>

java.lang.Object

org.key_project.util.collection.ImmutableLeftistHeap<S>

org.key_project.util.collection.ImmutableLeftistHeap.Node<S>

All Implemented Interfaces:

java.io.Serializable, java.lang.Iterable<S>, ImmutableHeap<S>

Enclosing class:

ImmutableLeftistHeap<T extends java.lang.Comparable<T>>

private static class ImmutableLeftistHeap.Node<S extends java.lang.Comparable<S>>
extends ImmutableLeftistHeap<S>

Class for non-empty heaps

Field Summary

Fields

Modifier and Type	Field and Description
private S	data
private ImmutableLeftistHeap<S>	left Children of the root of this heap
private ImmutableLeftistHeap<S>	right
private int	rightHeight Length of the right spine, i.e. the length of the path from the root to rightmost leaf
private static long	serialVersionUID
private int	size

Constructor Summary

Constructors

Modifier	Constructor and Description
	Node(S element) Node constructor for nodes with only empty children
	Node(S element, ImmutableLeftistHeap<S> a) Node constructor for nodes with at most one non-empty child
private	Node(S element, ImmutableLeftistHeap<S> a, ImmutableLeftistHeap<S> b) Node constructor for nodes

Method Summary

Modifier and Type	Method and Description
ImmutableHeap<S>	deleteMin() Remove the minimum element from this heap
S	findMin()
protected int	getRightHeight() Length of the right spine, i.e. the length of the path from the root to rightmost leaf
ImmutableHeap<S>	insert(ImmutableHeap<S> h) Add multiple elements to this heap object
ImmutableHeap<S>	insert(S element) Add an element to this heap object
boolean	isEmpty()
ImmutableHeap<S>	removeAll(S element) Remove all elements of this heap which are equal to element.
int	size()

Methods inherited from class org.key_project.util.collection.ImmutableLeftistHeap

insert, iterator, nilHeap, sortedIterator, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Field Detail

serialVersionUID

private static final long serialVersionUID

See Also:

Constant Field Values

rightHeight

private final int rightHeight

Length of the right spine, i.e. the length of the path from the root to rightmost leaf

size

private final int size

data

private final S extends java.lang.Comparable<S> data

left

private final ImmutableLeftistHeap<S extends java.lang.Comparable<S>> left

Children of the root of this heap

right

private final ImmutableLeftistHeap<S extends java.lang.Comparable<S>> right

Constructor Detail

Node

public Node(S element)

Node constructor for nodes with only empty children

Node

public Node(S element,
            ImmutableLeftistHeap<S> a)

Node constructor for nodes with at most one non-empty child

Node

private Node(S element,
             ImmutableLeftistHeap<S> a,
             ImmutableLeftistHeap<S> b)

Node constructor for nodes

Method Detail

getRightHeight

protected int getRightHeight()

Length of the right spine, i.e. the length of the path from the root to rightmost leaf

Specified by:

getRightHeight in class ImmutableLeftistHeap<S extends java.lang.Comparable<S>>

isEmpty

public boolean isEmpty()

Returns:

true iff this heap is empty

insert

public ImmutableHeap<S> insert(S element)

Add an element to this heap object

Parameters:

element - the element to be added

Returns:

a heap that contains all elements of this heap, and additionally element

insert

public ImmutableHeap<S> insert(ImmutableHeap<S> h)

Add multiple elements to this heap object

Parameters:

h - a heap containing the elements to be added

Returns:

a heap that contains all elements of this heap, and additionally all objects from h

findMin

public S findMin()

Returns:

the minimum element of this heap, or null iff this heap is empty (isEmpty()==true)

deleteMin

public ImmutableHeap<S> deleteMin()

Remove the minimum element from this heap

Returns:

a heap that contains all elements of this heap except for the minimum element

removeAll

public ImmutableHeap<S> removeAll(S element)

Remove all elements of this heap which are equal to element.

Returns:

heap that has all occurrences of element removed

size

public int size()

Returns:

the number of elements this heap holds