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

Class DoubleIntegerMaxHeap

java.lang.Object

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

All Implemented Interfaces:

DoubleIntegerHeap

public class DoubleIntegerMaxHeap
extends java.lang.Object
implements DoubleIntegerHeap

Binary heap for double keys and int values. This class is generated from a template.

Since:

0.6.0

Author:

Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
private class	DoubleIntegerMaxHeap.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 double[]	twoheap Base heap.
protected int[]	twovals Base heap values.

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
void	add(double o, int v) Add a key-value pair to the heap
void	add(double key, int val, int max) Add a key-value pair to the heap if it improves the top.
void	clear() Clear the heap contents.
boolean	containsKey(double q) Contains operation for a key (slow: with a linear scan).
boolean	containsValue(int q) Contains operation for a value (slow: with a linear scan).
private void	heapifyDown(double cur, int val) Invoke heapify-down for the root object.
private void	heapifyUp(int twopos, double cur, int val) Heapify-Up method for 2-ary heap.
boolean	isEmpty() Is the heap empty?
double	peekKey() Get the current top key.
int	peekValue() Get the current top value.
void	poll() Remove the first element.
void	replaceTopElement(double reinsert, int val) Combined operation that removes the top element, and inserts a new element instead.
int	size() Query the size.
java.lang.String	toString()
DoubleIntegerMaxHeap.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 double[] twoheap

Base heap.

twovals

protected int[] 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

DoubleIntegerMaxHeap

public DoubleIntegerMaxHeap()

Constructor, with default size.

DoubleIntegerMaxHeap

public DoubleIntegerMaxHeap(int minsize)

Constructor, with given minimum size.

Parameters:

minsize - Minimum size

Method Detail

clear

public void clear()

Description copied from interface: DoubleIntegerHeap

Clear the heap contents.

Specified by:

clear in interface DoubleIntegerHeap

size

public int size()

Description copied from interface: DoubleIntegerHeap

Query the size.

Specified by:

size in interface DoubleIntegerHeap

Returns:

Size

isEmpty

public boolean isEmpty()

Description copied from interface: DoubleIntegerHeap

Is the heap empty?

Specified by:

isEmpty in interface DoubleIntegerHeap

Returns:

true when the size is 0.

add

public void add(double o,
                int v)

Description copied from interface: DoubleIntegerHeap

Add a key-value pair to the heap

Specified by:

add in interface DoubleIntegerHeap

Parameters:

o - Key

v - Value

add

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

Description copied from interface: DoubleIntegerHeap

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

Specified by:

add in interface DoubleIntegerHeap

Parameters:

key - Key

val - Value

max - Desired maximum size

replaceTopElement

public void replaceTopElement(double reinsert,
                              int val)

Description copied from interface: DoubleIntegerHeap

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

Specified by:

replaceTopElement in interface DoubleIntegerHeap

Parameters:

reinsert - Key of new element

val - Value of new element

heapifyUp

private void heapifyUp(int twopos,
                       double cur,
                       int 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: DoubleIntegerHeap

Remove the first element.

Specified by:

poll in interface DoubleIntegerHeap

heapifyDown

private void heapifyDown(double cur,
                         int val)

Invoke heapify-down for the root object.

Parameters:

cur - Object to insert.

val - Value to reinsert.

peekKey

public double peekKey()

Description copied from interface: DoubleIntegerHeap

Get the current top key.

Specified by:

peekKey in interface DoubleIntegerHeap

Returns:

Top key

peekValue

public int peekValue()

Description copied from interface: DoubleIntegerHeap

Get the current top value.

Specified by:

peekValue in interface DoubleIntegerHeap

Returns:

Value

containsKey

public boolean containsKey(double q)

Description copied from interface: DoubleIntegerHeap

Contains operation for a key (slow: with a linear scan).

Specified by:

containsKey in interface DoubleIntegerHeap

Parameters:

q - Key

Returns:

true if the key is contained in the heap.

containsValue

public boolean containsValue(int q)

Description copied from interface: DoubleIntegerHeap

Contains operation for a value (slow: with a linear scan).

Specified by:

containsValue in interface DoubleIntegerHeap

Parameters:

q - Value

Returns:

true if the value is contained in the heap.

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

unsortedIter

public DoubleIntegerMaxHeap.UnsortedIter unsortedIter()

Description copied from interface: DoubleIntegerHeap

Get an unsorted iterator to inspect the heap.

Specified by:

unsortedIter in interface DoubleIntegerHeap

Returns:

Iterator