de.lmu.ifi.dbs.elki.utilities.datastructures.heap

Class IntegerObjectMaxHeap<V>

java.lang.Object

de.lmu.ifi.dbs.elki.utilities.datastructures.heap.IntegerObjectMaxHeap<V>

Type Parameters:

V - Value type

All Implemented Interfaces:

IntegerObjectHeap<V>

public class IntegerObjectMaxHeap<V>
extends Object
implements IntegerObjectHeap<V>

Binary heap for primitive types.

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	IntegerObjectMaxHeap.UnsortedIter Unsorted iterator - in heap order.

Field Summary

Fields

Modifier and Type	Field and Description
protected int	size Current size of heap.
private static int	TWO_HEAP_INITIAL_SIZE Initial size of the 2-ary heap.
protected int[]	twoheap Base heap.
protected Object[]	twovals Base heap values.

Constructor Summary

Constructors

Constructor and Description
IntegerObjectMaxHeap() Constructor, with default size.
IntegerObjectMaxHeap(int minsize) Constructor, with given minimum size.

Method Summary

Methods

Modifier and Type	Method and Description
void	add(int o, V v) Add a key-value pair to the heap
void	add(int key, V val, int max) Add a key-value pair to the heap if it improves the top.
void	clear() Clear the heap contents.
private void	heapifyDown(int cur, Object val) Invoke heapify-down for the root object.
private void	heapifyUp(int twopos, int cur, Object val) Heapify-Up method for 2-ary heap.
boolean	isEmpty() Is the heap empty?
int	peekKey() Get the current top key
V	peekValue() Get the current top value
void	poll() Remove the first element
void	replaceTopElement(int reinsert, V val) Combined operation that removes the top element, and inserts a new element instead.
int	size() Query the size
String	toString()
IntegerObjectMaxHeap.UnsortedIter	unsortedIter() Get an unsorted iterator to inspect the heap.

Methods inherited from class java.lang.Object

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

Field Detail

twoheap

protected int[] twoheap

Base heap.

twovals

protected Object[] twovals

Base heap values.

size

protected int size

Current size of heap.

TWO_HEAP_INITIAL_SIZE

private static final int TWO_HEAP_INITIAL_SIZE

Initial size of the 2-ary heap.

See Also:

Constant Field Values

Constructor Detail

IntegerObjectMaxHeap

public IntegerObjectMaxHeap()

Constructor, with default size.

IntegerObjectMaxHeap

public IntegerObjectMaxHeap(int minsize)

Constructor, with given minimum size.

Parameters:

minsize - Minimum size

Method Detail

clear

public void clear()

Description copied from interface: IntegerObjectHeap

Clear the heap contents.

Specified by:

clear in interface IntegerObjectHeap<V>

size

public int size()

Description copied from interface: IntegerObjectHeap

Query the size

Specified by:

size in interface IntegerObjectHeap<V>

Returns:

Size

isEmpty

public boolean isEmpty()

Description copied from interface: IntegerObjectHeap

Is the heap empty?

Specified by:

isEmpty in interface IntegerObjectHeap<V>

Returns:

true when the size is 0.

add

public void add(int o,
       V v)

Description copied from interface: IntegerObjectHeap

Add a key-value pair to the heap

Specified by:

add in interface IntegerObjectHeap<V>

Parameters:

o - Key

v - Value

add

public void add(int key,
       V val,
       int max)

Description copied from interface: IntegerObjectHeap

Add a key-value pair to the heap if it improves the top.

Specified by:

add in interface IntegerObjectHeap<V>

Parameters:

key - Key

val - Value

max - Desired maximum size

replaceTopElement

public void replaceTopElement(int reinsert,
                     V val)

Description copied from interface: IntegerObjectHeap

Combined operation that removes the top element, and inserts a new element instead.

Specified by:

replaceTopElement in interface IntegerObjectHeap<V>

Parameters:

reinsert - Key of new element

val - Value of new element

heapifyUp

private void heapifyUp(int twopos,
             int cur,
             Object val)

Heapify-Up method for 2-ary heap.

Parameters:

twopos - Position in 2-ary heap.

cur - Current object

val - Current value

poll

public void poll()

Description copied from interface: IntegerObjectHeap

Remove the first element

Specified by:

poll in interface IntegerObjectHeap<V>

heapifyDown

private void heapifyDown(int cur,
               Object val)

Invoke heapify-down for the root object.

Parameters:

cur - Object to insert.

val - Value to reinsert.

peekKey

public int peekKey()

Description copied from interface: IntegerObjectHeap

Get the current top key

Specified by:

peekKey in interface IntegerObjectHeap<V>

Returns:

Top key

peekValue

public V peekValue()

Description copied from interface: IntegerObjectHeap

Get the current top value

Specified by:

peekValue in interface IntegerObjectHeap<V>

Returns:

Value

toString

public String toString()

Overrides:

toString in class Object

unsortedIter

public IntegerObjectMaxHeap.UnsortedIter unsortedIter()

Description copied from interface: IntegerObjectHeap

Get an unsorted iterator to inspect the heap.

Specified by:

unsortedIter in interface IntegerObjectHeap<V>

Returns:

Iterator