jvx.util

Class PuPriorityQueue

java.lang.Object

jv.object.PsObject

jvx.util.PuPriorityQueue

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, PsUpdateIf

public final class PuPriorityQueue
extends PsObject

Integer heap with double keys (resp. weights) based on following special property: The ints given to the heap must be the numbers from 0 to capacity-1 and each int can be in the heap just once. As a result methods like isElement() run in O(1) time.

We call the integers in the heap elements.

Heap is used e.g. to compute a minimum spanning tree on the vertices resp. faces of a geometry with weight assigned to each edge (cp. Prim's algorithm for minimal spanning trees).

See Also:

Serialized Form

Author:

Klaus Hildebrandt

Version:

01.03.07, 2.01 revised (mn) Added field m_capacity.
09.12.06, 2.00 revised (kp) Moved to jvx.util from jvx.geom.
07.08.06, 1.30 revised (fk) New methods toString and #extractElement(int) extractElement}.
20.01.05, 1.20 revised (ep) New methods increaseKey and changeKey.
12.02.04, 1.10 revised (kh) Renamed data[][] to m_positions and m_elements.
00.01.03, 1.00 created (kh)

Field Summary

Fields inherited from class jv.object.PsObject

HAS_BOUNDARY_PANEL, HAS_CONFIG_PANEL, HAS_INFO_PANEL, HAS_LABEL_PANEL, HAS_MATERIAL_PANEL, HAS_TEXTURE_PANEL, HAS_VECTOR_PANEL, INSPECTOR_INFO, INSPECTOR_INFO_EXT, IS_DELETED, IS_FIXED, IS_FOCUSSED, IS_PICKED, IS_SELECTED, IS_USED, NUM_TAGS

Constructor Summary

Constructors

Constructor and Description
PuPriorityQueue(double[] key) Create a priority queue that has the elements 0...key.length and the given keys.
PuPriorityQueue(int capacity) Create an empty priority queue with a given capacity.
PuPriorityQueue(int capacity, double key) Create a priority queue containing the elements 0,1,2,...capacity-1.

Method Summary

Modifier and Type	Method and Description
boolean	changeKey(int element, double key) Changes the key assigned to an element and reorder the heap.
java.lang.Object	clone() Create a copy of the heap.
boolean	decreaseKey(int element, double key) Decrease the key assigned to an element and reorder the heap.
void	emptyHeap() Remove all elements from heap.
boolean	enqueue(int element, double key) Add element to heap.
boolean	enqueueOrDecrease(int element, double key) Add element to heap.
double	extractElement(int element) Remove a specific element from the heap and return its key.
int	extractMin() Extract the element with the smallest key of the heap.
int	getCapacity() Maximal heap size for this heap.
int	getElement(int position) Method returns the index of the element at the specified position.
int[]	getElements() Get the array, where the heap stores the elements.
int	getHeapSize() Get the number of Elements in the heap.
double	getKey(int element) Method returns the key of the specified element.
double	getKeyOfMin() Get key of minimal element.
double[]	getKeys() Get the array containing the key of each element.
int	getPosition(int element) Method returns the position of the specified element in the heap.
int[]	getPositions() Get the array, where the heap stores the positions of the elements.
boolean	increaseKey(int element, double key) Increases the key assigned to an element and reorder the heap.
boolean	isElement(int element) Check if element i is in the heap.
boolean	isEmpty() Returns true, if there is no element in the heap.
java.lang.String	toString() Create a multi-line string representation with detailed information about instance variables.

Methods inherited from class jv.object.PsObject

addInspector, addUpdateListener, assureInspector, clearTag, clone, clone, copy, getFather, getInfoPanel, getInspector, getName, getNumObjects, getSymbol, hasInspector, hasTag, hasUpdateListener, init, instanceOf, instanceOf, newInspector, newInspector, removeInspector, removeInspector, removeUpdateListener, setName, setParent, setSymbol, setTag, update, updatePanels

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

PuPriorityQueue

public PuPriorityQueue(int capacity)

Create an empty priority queue with a given capacity.

PuPriorityQueue

public PuPriorityQueue(double[] key)

Create a priority queue that has the elements 0...key.length and the given keys.

PuPriorityQueue

public PuPriorityQueue(int capacity,
                       double key)

Create a priority queue containing the elements 0,1,2,...capacity-1. All elements get the same (given) key.

Method Detail

getCapacity

public int getCapacity()

Maximal heap size for this heap.

getElements

public int[] getElements()

Get the array, where the heap stores the elements.

getElement

public int getElement(int position)

Method returns the index of the element at the specified position.

getPositions

public int[] getPositions()

Get the array, where the heap stores the positions of the elements.

getPosition

public int getPosition(int element)

Method returns the position of the specified element in the heap. If the element is not in the heap, -1 is returned.

getKeys

public double[] getKeys()

Get the array containing the key of each element.

getKey

public double getKey(int element)

Method returns the key of the specified element. Method returns the key even if the element has already been extracted from the heap.

decreaseKey

public boolean decreaseKey(int element,
                           double key)

Decrease the key assigned to an element and reorder the heap. If the key is bigger than the actual key of the element nothing is done.

Returns:

false if element does not exist or its key is smaller than parameter key

increaseKey

public boolean increaseKey(int element,
                           double key)

Increases the key assigned to an element and reorder the heap. If the key is smaller than the actual key of the element, nothing is done.

Returns:

false if element does not exist or its key is greater than parameter key

changeKey

public boolean changeKey(int element,
                         double key)

Changes the key assigned to an element and reorder the heap.

Returns:

false if element does not exist

Author:

Eike Preuss

Version:

20.01.05, 1.00 created (ep)

getKeyOfMin

public double getKeyOfMin()

Get key of minimal element.

extractMin

public int extractMin()

Extract the element with the smallest key of the heap. To get the key of the element use getKey(int).

extractElement

public double extractElement(int element)

Remove a specific element from the heap and return its key. If the specified element index is out of range, NaN is returned.

Parameters:

element - index of the element to extract.

Returns:

Key of the extracted element, or NaN if argument is no queue element.

Author:

Felix Kaelberer

Version:

07.08.2006, 1.00 created (fk)

getHeapSize

public int getHeapSize()

Get the number of Elements in the heap.

isEmpty

public boolean isEmpty()

Returns true, if there is no element in the heap.

clone

public java.lang.Object clone()

Create a copy of the heap.

Overrides:

clone in class PsObject

See Also:

PsObject.copy(PsObject)

isElement

public boolean isElement(int element)

Check if element i is in the heap.

enqueue

public boolean enqueue(int element,
                       double key)

Add element to heap. If element is already in the heap nothing is done and false is returned.

enqueueOrDecrease

public boolean enqueueOrDecrease(int element,
                                 double key)

Add element to heap. If the element is already in the heap and the given key is smaller than the actual key, decrease its key.

emptyHeap

public void emptyHeap()

Remove all elements from heap.

toString

public java.lang.String toString()

Create a multi-line string representation with detailed information about instance variables.

Overrides:

toString in class PsObject

Author:

Felix Kaelberer

Version:

07.08.2006, 1.00 created (fk)